D. Dumitriu, S. Funke and N. Milosavljevic. How Much Geometry It Takes to Reconstruct a 2-Manifold in R^3. ACM Journal of Experimental Algorithmics (JEA), volume 13, February 2009.

Abstract:

Known algorithms for reconstructing a 2-manifold from a point sample in R^3 are naturally based on decisions/predicates that take the geometry of the point sample into account. Facing the always present problem of round-off errors that easily compromise the exactness of those predicate decisions, an exact and robust implementation of these algorithms is far from being trivial and typically requires employment of advanced datatypes for exact arithmetic, as provided by libraries like CORE [Karamcheti et al. 1999], LEDA [Mehlhorn et al. 1997] or GMP [gmp]. In this paper we present a new reconstruction algorithm, one of whose main novelties is to throw away geometry information early on in the reconstruction process and to mainly operate combinatorially on a graph structure. More precisely, our algorithm only requires distances between the sample points and not the actual embedding in R^3. As such it is less susceptible to robustness problems due to round-off errors and also benefits from not requiring expensive exact arithmetic by faster running times. A more theoretical view on our algorithm including correctness proofs under suitable sampling conditions can be found in a companion paper [Dumitriu et al. 2008].

Bibtex: 

@article{dfm-hmgitr2r-09,
	author="Daniel Dumitriu and Stefan Funke and Nikola Milosavljevi\'c",
	title="How Much Geometry It Takes to Reconstruct a 2-Manifold in R^3",
	journal="ACM Journal of Experimental Algorithmics (JEA)"
	month="February",
	year="2009"
}