Robust construction or the three-dimensional flow complex

F. Cazals, A. Parameswaran, S. Pion

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The Delaunay triangulation and its dual the Voronoi diagram are ubiquitous geometric complexes. From a topological standpoint, the connection has recently been made between these cell complexes and the Morse theory of distance functions. In particular, in the generic setting, algorithms have been proposed to compute the flow complex -the stable and unstable manifolds associated to the critical points of the distance function to a point set. As algorithms ignoring degenerate cases and numerical issues are bound to fail on general inputs, this paper develops the first complete and robust algorithm to compute the flow complex. First, we present complete algorithms for the flow operator, unraveling a delicate interplay between the degenerate cases of Delaunay and those which are flow specific. Second, we sketch how^ the flow operator unifies the construction of stable and unstable manifolds. Third, we discuss numerical issues related to predicates on cascaded constructions. Finally, we report experimental results with CGAL's filtered kernel, showing that the construction of the flow complex incurs a small overhead w.r.t. the Delaunay triangulation when moderate cascading occurs. These observations provide important insights on the relevance of the flow complex for (surface) reconstruction and medial axis approximation, and should foster flow complex based algorithms. In a broader perspective and to the best of our knowledge, this paper is the first one reporting on the effective implementation of a geometric algorithm featuring cascading.

Original languageEnglish (US)
Title of host publicationProceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08
Pages182-191
Number of pages10
DOIs
StatePublished - Dec 12 2008
Event24th Annual Symposium on Computational Geometry, SCG'08 - College Park, MD, United States
Duration: Jun 9 2008Jun 11 2008

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other24th Annual Symposium on Computational Geometry, SCG'08
CountryUnited States
CityCollege Park, MD
Period6/9/086/11/08

Keywords

  • Euclidean distance function
  • Lazy constructions, cascading
  • Medial axis approximation
  • Morse-smale complex
  • Surface reconstruction

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Robust construction or the three-dimensional flow complex'. Together they form a unique fingerprint.

  • Cite this

    Cazals, F., Parameswaran, A., & Pion, S. (2008). Robust construction or the three-dimensional flow complex. In Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08 (pp. 182-191). (Proceedings of the Annual Symposium on Computational Geometry). https://doi.org/10.1145/1377676.1377705