Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop
Show entries of:
this year
(2020) |
last year
(2019) |
two years ago
(2018) |
Notes URL
Action:
login to update
Options:
Goto entry point
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, Joachim
dblp
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
URL of the conference:
http://www.dmist.net/swat2008/
URL for downloading the paper:
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-ﬁltering like CRUST or CoCone still
require -- after identifying a set of candidate triangles -- a so-called manifold extraction step which identiﬁes a subset of the candidate triangles to form the ﬁnal reconstruction surface. Non-locality of the latter step is caused by so-called slivers -- conﬁgurations 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
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
Attachment Section
Attachment Section