English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  On the Locality of Extracting a 2-Manifold in IR3

Dumitriu, D., Funke, S., Kutz, M., & Milosavljevic, N. (2008). On the Locality of Extracting a 2-Manifold in IR3. In J. Gudmundsson (Ed.), Algorithm Theory – SWAT 2008 (pp. 270-281). Berlin: Springer. doi:10.1007/978-3-540-69903-3_25.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-1C80-F Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0028-F32A-D
Genre: Conference Paper
Latex : On the Locality of Extracting a 2-Manifold in {IR}3

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Dumitriu, Daniel1, Author           
Funke, Stefan1, Author           
Kutz, Martin1, Author           
Milosavljevic, Nikola1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2009-04-0320082008
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 428046
DOI: 10.1007/978-3-540-69903-3_25
URI: http://dx.doi.org/10.1007/978-3-540-69903-3_25
Other: Local-ID: C125756E0038A185-1DDDB2ECAACD1503C125748D003232B1-DFKM2008b
 Degree: -

Event

show
hide
Title: 11th Scandinavian Workshop on Algorithm Theory
Place of Event: Göteborg, Sweden
Start-/End Date: 2008-07-02 - 2008-07-04

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithm Theory – SWAT 2008
  Subtitle : 11th Scandinavian Workshop on Algorithm Theory, Gothenburg, Sweden, July 2-4, 2008. Proceedings
  Abbreviation : SWAT 2008
Source Genre: Proceedings
 Creator(s):
Gudmundsson, Joachim1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 270 - 281 Identifier: ISBN: 978-3-540-69900-2

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 5124 Sequence Number: - Start / End Page: - Identifier: -