English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse
  1. Item Summary / 
  2. View item

Item

ITEM ACTIONSEXPORT
Add to Basket
 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

Basic

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

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

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

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

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

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

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: -