Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

On the Locality of Extracting a 2-Manifold in IR3

MPG-Autoren
/persons/resource/persons44353

Dumitriu,  Daniel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44464

Funke,  Stefan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44874

Kutz,  Martin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45051

Milosavljevic,  Nikola
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte in PuRe verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-000F-1C80-F
Zusammenfassung
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.