Abstract Smooth-Surface Reconstruction in Near-Linear Time

A surface reconstruction algorithm takes as input a set of sample points from an unknown closed and smooth surface in 3-d space, and produces a piece-wise linear approximation of the surface that contains the sample points. Recently, several algorithms with a correctness guarantee have been proposed. They have unfortunately a worst-case running time that is quadratic in the size of the input because they are based on the construction of 3-d Voronoi diagrams or Delaunay tetrahedrizations which can have quadratic size. In this paper, we describe a new algorithm that also has a correctness guarantee but whose worst-case running time is ¢¤£¦¥¨§�©���¥� � where ¥ is the input size. This is actually optimal. As in some of the previous algorithms, the piece-wise linear approximation produced by the new algorithm is a triangulation which is a subset of the 3-d Delaunay tetrahedrization.