
D. Dumitriu, S. Funke, M. Kutz, N. Milosavljevic. On the Locality of Extracting a 2Manifold in R^3. Accepted at the 11th Scandinavian Workshop on Algorithm Theory (SWAT) 2008, preliminary version at the 24th European Workshop on Computational Geometry (EWCG) 2008.
Abstract:
Algorithms for reconstructing a 2manifold from a point sample in R^3 based on Voronoifiltering like CRUST or CoCone still require – after identifying a set of candidate triangles – a socalled manifold extraction step which identifies a subset of the candidate triangles to form the final reconstruction surface. Nonlocality of the latter step is caused by socalled slivers – configurations of 4 almost cocircular points having an empty circumsphere with center close to the manifold surface. We prove that under a certain mild condition – local uniformity – which typically holds in practice but can also be enforced theoretically, one can compute a reconstruction using an algorithm whose decisions about the adjacencies of a point only depend on nearby points.
While the theoretical proof requires an extremely high sampling density, our prototype implementation, described in a companion paper, preforms well on typical sample sets. Due to its local mode of computation, it might be particularly suited for parallel computing or external memory scenarios.
Bibtex:
@inproceedings{dfkmole2r08,
author="Daniel Dumitriu and Stefan Funke and Martin Kutz and Nikola Milosavljevi\'c",
title="On the Locality of Extracting a 2Manifold in R^3",
booktitle="Proc. of the 11th Scandinavian Workshop on Algorithm Theory (SWAT)"
month="July",
year="2008"
}

