2026-07-23T12:54:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17357 2024-03-06T10:59:32Z ddc:004 open_access

A Finite Algorithm for the Realizabilty of a Delaunay Triangulation Agrawal, Akanksha Saurabh, Saket Zehavi, Meirav Delaunay Triangulation Delaunay Realization Finite Algorithm Integer Coordinate Realization The Delaunay graph of a point set P ⊆ ℝ² 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 ⊆ ℝ², called a Delaunay triangulation of P, that is isomorphic to G. The objective of Delaunay Realization is to compute a point set P ⊆ ℝ² 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. [Hiroshima et al., 2000]. We design an n^𝒪(n)-time constructive algorithm for Delaunay Realization. In fact, our algorithm outputs sets of points with integer coordinates. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Akanksha Agrawal and Saket Saurabh and Meirav Zehavi 2022 Is Part Of LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2022.1 urn:nbn:de:0030-drops-173573 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.1 eng https://creativecommons.org/licenses/by/4.0/legalcode