# Constructing Intrinsic Delaunay Triangulations from the Dual of Geodesic Voronoi Diagrams

arXiv: https://arxiv.org/abs/1505.05590 · HTML: https://mlsanity.com/paper/1505.05590/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 May 2015.

## Built on by (most cited first, 1 of 1)

- [Weighted Poisson-disk Resampling on Large-Scale Point Clouds](https://mlsanity.com/paper/2412.09177/) (2024)

## Abstract (arXiv)

Intrinsic Delaunay triangulation (IDT) is a fundamental data structure in computational geometry and computer graphics. However, except for some theoretical results, such as existence and uniqueness, little progress has been made towards computing IDT on simplicial surfaces. To date the only way for constructing IDTs is the edge-flipping algorithm, which iteratively flips the non-Delaunay edge to be locally Delaunay. Although the algorithm is conceptually simple and guarantees to stop in finite steps, it has no known time complexity. Moreover, the edge-flipping algorithm may produce non-regular triangulations, which contain self-loops and/or faces with only two edges. In this paper, we propose a new method for constructing IDT on manifold triangle meshes. Based on the duality of geodesic Voronoi diagrams, our method can guarantee the resultant IDTs are regular. Our method has a theoretical worst-case time complexity O(n2log n) for a mesh with n vertices. We observe that most real-world models are far from their Delaunay triangulations, thus, the edge-flipping algorithm takes many iterations to fix the non-Delaunay edges. In contrast, our method is non-iterative and insensitive to the number of non-Delaunay edges. Empirically, it runs in linear time O(n) on real-world models.