A Finite Algorithm for the Realizabilty of a Delaunay Triangulation

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.