Surface Reconstruction in almost Linear Time under Locally Uniform Sampling

Tamal Dey, Stefan Funke, Edgar Ramos

We describe a new variant of the Cocone algorithm for smooth surface reconstruction by Amenta et al (2000). This variant runs in $O(n \log n)$ time if the sample is ``locally uniform'' in addition to being good in the sense required for the Cocone algorithm. If the local uniformity condition does not hold, the algorithm still produces a correct result and its worst case running time is $O(n^2\log n)$. In contrast, the original algorithm requires $\Omega(n^2)$ time in the worst case, even if the sample is locally uniform.

Proc. 17th European Workshop on Computational Geometry (EWCG) 2001, Berlin