A new Voronoi-based surface reconstruction algorithm

We describe our experience with a new algorithm for the reconstruction of surfaces from unorganized sample points in IR 3 . The al- gorithm is the first for this problem with provable guarantees. Given a "good sample" from a smooth surface, the output is guaranteed to be topologically correct and convergent to the original surface as the sampling density increases. The definition of a good sample is itself interesting: the required sampling density varies locally, rigorously capturing the intuitive notion that featureless areas can be reconstructed from fewer samples. The output mesh interpolates, rather than approximates, the input points.