A Finite Algorithm for the Realizabilty of a Delaunay Triangulation

The Delaunay graph of a point set P ⊆ R2 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 ⊆ R2, called a Delaunay triangulation of P, that is isomorphic to G. The objective of Delaunay Realization is to compute a point set P ⊆ R2 that realizes a given graph G (if such a P exists). Known algorithms do not solve Delaunay Realization as they are non-constructive. Obtaining a constructive algorithm for Delaunay Realization was mentioned as an open problem by Hiroshima et al. [19]. We design an nO(n)-time constructive algorithm for Delaunay Realization. In fact, our algorithm outputs sets of points with integer coordinates.