### 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08 |

Pages | 182-191 |

Number of pages | 10 |

DOIs | |

State | Published - Dec 12 2008 |

Event | 24th Annual Symposium on Computational Geometry, SCG'08 - College Park, MD, United States Duration: Jun 9 2008 → Jun 11 2008 |

### Publication series

Name | Proceedings of the Annual Symposium on Computational Geometry |
---|

### Other

Other | 24th Annual Symposium on Computational Geometry, SCG'08 |
---|---|

Country | United States |

City | College Park, MD |

Period | 6/9/08 → 6/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

*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