Electronic Journal Article
@Article
Zeitschriftenartikel in einem e-Journal



Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Dumitriu, Daniel
Funke, Stefan
Kutz, Martin
Milosavljevic, Nikola

dblp
dblp
dblp
dblp

Not MPG Author(s):

Dumitriu, Daniel
Funke, Stefan
Kutz, Martin
Milosavljevic, Nikola

BibTeX cite key*:

DFKM2009

Title

Title*:

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

Journal

Journal Title*:

ACM Journal of Experimental Algorithms

Journal's URL:

http://jea.acm.org/

Download URL
for the article:

http://doi.acm.org/10.1145/1498698.1537597

Language:

English

Publisher

Publisher's
Name:

ACM

Publisher's URL:

http://www.acm.org/

Publisher's
Address:

New York, NY

ISSN:

1084-6654

Vol, No, Year, pp.

Volume:

14

Number:


Month:

May

Year*:

2009

Pages:

2.2:1-2.2:17

Number of VG Pages:


Sequence Number:

2.2

DOI:

10.1145/1498698.1537597

Abstract, Links, (C)

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

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@MISC{DFKM2009,
AUTHOR = {Dumitriu, Daniel and Funke, Stefan and Kutz, Martin and Milosavljevic, Nikola},
TITLE = {How Much Geometry It Takes to Reconstruct a 2-Manifold in {R} 3},
JOURNAL = {ACM Journal of Experimental Algorithms},
PUBLISHER = {ACM},
YEAR = {2009},
VOLUME = {14},
PAGES = {2.2:1--2.2:17},
ADDRESS = {New York, NY},
MONTH = {May},
ISBN = {1084-6654},
DOI = {10.1145/1498698.1537597},
}


Entry last modified by Anja Becker, 01/19/2011
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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)
[Library]
Created
07/06/2009 12:08:54 PM
Revisions
3.
2.
1.
0.
Editor(s)
Anja Becker
Anja Becker
Anja Becker
Daniel Dumitriu
Edit Dates
19.01.2011 16:01:08
16.12.2010 11:00:45
04.03.2010 15:26:05
07/06/2009 12:08:54 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section