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.
Type de document :
Communication dans un congrès
ACM Symposium on Computational Geometry (SCG), Jun 2008, Washington, United States. 2008
Liste complète des métadonnées
Contributeur : Sylvain Pion <>
Soumis le : lundi 8 décembre 2008 - 00:04:28
Dernière modification le : samedi 27 janvier 2018 - 01:31:48
Document(s) archivé(s) le : mardi 28 juin 2011 - 18:11:49


Fichiers produits par l'(les) auteur(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. 2008. 〈inria-00344962〉



Consultations de la notice


Téléchargements de fichiers