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):
Gudmundsson, Joachimdblp
Not MPII Editor(s):
Gudmundsson, Joachim
BibTeX cite key*:
DFKM2008b
Title, Booktitle
Title*:
On the Locality of Extracting a 2-Manifold in $R^3$
Booktitle*:
11th Scandinavian Workshop on Algorithm Theory (SWAT-2008)
Event, URLs
Conference URL::
http://www.dmist.net/swat2008/
Downloading URL:
Event Address*:
Göteborg, Sweden
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
2 July 2008
Event End Date:
4 July 2008
Publisher
Name*:
Springer
URL:
http://www.springer.com
Address*:
Heidelberg, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
5124
Number:
Month:
July
Pages:
270-281
Year*:
2008
VG Wort Pages:
ISBN/ISSN:
978-3-540-69900-2
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
Algorithms for reconstructing a 2-manifold from a point sample in R^3 based on Voronoi-filtering like CRUST or CoCone still
require -- after identifying a set of candidate triangles -- a so-called manifold extraction step which identifies a subset of the candidate triangles to form the final reconstruction surface. Non-locality of the latter step is caused by so-called slivers -- configurations of four almost cocircular points having an empty circumsphere with center close to the manifold surface.

We prove that under a certain mild condition -- local uniformity -- which typically holds in practice but can also be enforced theoretically, one can compute a reconstruction using an algorithm whose decisions about the adjacencies of a point only depend on nearby points.

While the theoretical proof requires an extremely high sampling density, our prototype implementation, described in a companion paper, performs well on typical sample sets. Due to its local mode of computation, it might be particularly suited for parallel computing or external memory scenarios.
Keywords:
surface reconstruction, combinatorial reconstruction, slivers
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{DFKM2008b,
AUTHOR = {Dumitriu, Daniel and Funke, Stefan and Kutz, Martin and Milosavljevic, Nikola},
EDITOR = {Gudmundsson, Joachim},
TITLE = {On the Locality of Extracting a 2-Manifold in $R^3$},
BOOKTITLE = {11th Scandinavian Workshop on Algorithm Theory (SWAT-2008)},
PUBLISHER = {Springer},
YEAR = {2008},
VOLUME = {5124},
PAGES = {270--281},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {G{\"o}teborg, Sweden},
MONTH = {July},
ISBN = {978-3-540-69900-2},
}


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
07/21/2008 11:08:17 AM
Revisions
2.
1.
0.

Editor(s)
Stefan Funke
Stefan Funke
Daniel Dumitriu

Edit Dates
03/26/2009 04:06:39 PM
03/24/2009 03:33:18 PM
07/21/2008 11:08:17 AM