Skip to Main content Skip to Navigation
Conference papers

Robust Construction of the Three-Dimensional Flow Complex

Frédéric Cazals 1 Aditya Parameswaran 1 Sylvain Pion 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Complete list of metadata
Contributor : Sylvain Pion Connect in order to contact the contributor
Submitted on : Monday, December 8, 2008 - 12:04:28 AM
Last modification on : Thursday, March 5, 2020 - 4:54:25 PM
Long-term archiving on: : Tuesday, June 28, 2011 - 6:11:49 PM


Files produced by the author(s)


  • 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⟩



Record views


Files downloads