Robust Construction of the Three-Dimensional Flow Complex - Archive ouverte HAL Access content directly
Conference Papers Year : 2008

Robust Construction of the Three-Dimensional Flow Complex

(1) , (1) , (1)
Frédéric Cazals
  • Function : Author
  • PersonId : 905122
Sylvain Pion


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.
Fichier principal
Vignette du fichier
socgfinal.pdf (427.59 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

inria-00344962 , version 1 (08-12-2008)


  • HAL Id : inria-00344962 , version 1


Frédéric Cazals, Aditya Parameswaran, Sylvain Pion. Robust Construction of the Three-Dimensional Flow Complex. ACM Symposium on Computational Geometry (SCG), Jun 2008, Washington, United States. ⟨inria-00344962⟩


224 View
234 Download


Gmail Facebook Twitter LinkedIn More