hide
Free keywords:
-
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.
