Visible neighborhood graph of point clouds

In this paper we present a new neighborhood graph definition of point clouds, called visible neighborhood graph. A local construction scheme using visibility information near each sample point is developed, and the neighbors are defined based on a convex hull computation in a dual space. Our method is able to approximate the underlying surface on which the point cloud was sampled, and can provide accurate neighborhoods in regions of close-by surface sheets. The theoretical guarantees of our method are proved, and the accuracy and efficiency of the graph are verified by experimental results. Its usefulness for applications such as geodesic computation and point cloud segmentation is also demonstrated.

Figure optionsDownload as PowerPoint slideHighlights
► A new neighborhood graph definition of point clouds is proposed.
► The graph is parameter-independent and can provide accurate neighborhoods.
► The neighbors are defined based on a convex hull computation in a dual space.
► The theoretical guarantees of our method are proved.
► An O(nlog n) algorithm is proposed to construct the graph.