MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Dumitriu, Daniel
Funke, Stefan
Kutz, Martin
Milosavljevic, Nikola
dblp
dblp
dblp
dblp
Not MPG Author(s):
Funke, Stefan
Kutz, Martin
Milosavljevic, Nikola
Editor(s):
BibTeX cite key*:
DFKM08
Title, Booktitle
Title*:
How much Geometry it takes to Reconstruct a 2-Manifold in $R^3$
Booktitle*:
10th Workshop on Algorithm Engineering and Experiments (ALENEX-2008)
Event, URLs
Conference URL::
http://www.siam.org/meetings/alenex08/
Downloading URL:
http://www.siam.org/proceedings/alenex/2008/alx08_07dumitriud.pdf
Event Address*:
San Francisco, USA
Language:
English
Event Date*
(no longer used):
Organization:
ACM-SIAM
Event Start Date:
19 January 2008
Event End Date:
19 January 2008
Publisher
Name*:
SIAM
URL:
Address*:
Philadelphia, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
65-74
Year*:
2008
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
Known algorithms for reconstructing a 2-manifold from
a point sample in R3 are naturally based on deci-
sions/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 predi-
cate decisions, an exact and robust implementation of these
algorithms is far from being trivial and typically requires
the employment of advanced datatypes for exact arithmetic
as provided by libraries like CORE, LEDA or GMP. In this
paper we present a new reconstruction algorithm, one of
whose main novelties is to throw away geometry informa-
tion early on in the reconstruction process and to mainly
operate combinatorially on a graph structure. 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 [3].
Keywords:
computational geometry, combinatorial surface reconstruction, graph
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{DFKM08,
AUTHOR = {Dumitriu, Daniel and Funke, Stefan and Kutz, Martin and Milosavljevic, Nikola},
TITLE = {How much {G}eometry it takes to {R}econstruct a 2-{M}anifold in $R^3$},
BOOKTITLE = {10th Workshop on Algorithm Engineering and Experiments (ALENEX-2008)},
PUBLISHER = {SIAM},
YEAR = {2008},
ORGANIZATION = {ACM-SIAM},
PAGES = {65--74},
ADDRESS = {San Francisco, USA},
}


Entry last modified by Stefan Funke, 03/26/2009
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Daniel Dumitriu
Created
01/23/2008 10:11:28 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Stefan Funke
Stefan Funke
Daniel Dumitriu
Daniel Dumitriu
Daniel Dumitriu
Edit Dates
03/26/2009 04:13:18 PM
03/24/2009 03:32:43 PM
01/23/2008 10:21:03 PM
01/23/2008 10:20:23 PM
01/23/2008 10:15:37 PM