English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

How Much Geometry It Takes to Reconstruct a 2-Manifold in R^3

MPS-Authors
/persons/resource/persons44353

Dumitriu,  Daniel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44464

Funke,  Stefan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44874

Kutz,  Martin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Dumitriu, D., Funke, S., Kutz, M., & Milosavjevic, N. (2009). How Much Geometry It Takes to Reconstruct a 2-Manifold in R^3. ACM Journal of Experimental Algorithms, 14, 2.2-2.17. doi:10.1145/1498698.1537597.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-1857-9
Abstract
Known algorithms for reconstructing a 2-manifold from a point sample in R3 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, LEDA, or GMP. In this article, we present a new reconstruction algorithm, one 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 R3. 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 article.