## 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.

PDF