Note: |
|
(LaTeX) 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. |
URL for the Abstract: |
|
Categories / Keywords: |
|
HyperLinks / References / URLs: |
|
Copyright Message: |
Permission to make digital or hard copies of part or all of this work for personal or classroom use
is granted without fee provided that copies are not made or distributed for profit or commercial
advantage and that copies show this notice on the first page or initial screen of a display along
with the full citation. Copyrights for components of this work owned by others than ACM must be
honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers,
to redistribute to lists, or to use any component of this work in other works requires prior specific
permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn
Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, or permissions@acm.org. |
Personal Comments: |
|
Download
Access Level: |
Public |
|
Edit History (please click the blue arrow to see the details)