# A Finite Algorithm for the Realizabilty of a Delaunay Triangulation

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

## Key facts

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

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

- [Optimal Bound for PCA with Outliers using Higher-Degree Voronoi Diagrams](https://mlsanity.com/paper/2408.06867/) (2024)

## Abstract (arXiv)

The Delaunay graph of a point set P subseteq ℝ2 is the plane graph with the vertex-set P and the edge-set that contains p,p' if there exists a disc whose intersection with P is exactly p,p'. Accordingly, a triangulated graph G is Delaunay realizable if there exists a triangulation of the Delaunay graph of some P subseteq ℝ2, called a Delaunay triangulation of P, that is isomorphic to G. The objective of textscDelaunay Realization is to compute a point set P subseteq ℝ2 that realizes a given graph G (if such a P exists). Known algorithms do not solve textscDelaunay Realization as they are non-constructive. Obtaining a constructive algorithm for textscDelaunay Realization was mentioned as an open problem by Hiroshima et al.~citehiroshima2000. We design an nO(n)-time constructive algorithm for textscDelaunay Realization. In fact, our algorithm outputs sets of points with em integer coordinates.