Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2022.1
URN: urn:nbn:de:0030-drops-173573
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17357/
Agrawal, Akanksha ; Saurabh, Saket ; Zehavi, Meirav
A Finite Algorithm for the Realizabilty of a Delaunay Triangulation
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{agrawal_et_al:LIPIcs.IPEC.2022.1,
author = {Agrawal, Akanksha and Saurabh, Saket and Zehavi, Meirav},
title = {{A Finite Algorithm for the Realizabilty of a Delaunay Triangulation}},
booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
pages = {1:1--1:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-260-0},
ISSN = {1868-8969},
year = {2022},
volume = {249},
editor = {Dell, Holger and Nederlof, Jesper},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17357},
URN = {urn:nbn:de:0030-drops-173573},
doi = {10.4230/LIPIcs.IPEC.2022.1},
annote = {Keywords: Delaunay Triangulation, Delaunay Realization, Finite Algorithm, Integer Coordinate Realization}
}
| Keywords: | Delaunay Triangulation, Delaunay Realization, Finite Algorithm, Integer Coordinate Realization | |
| Seminar: | 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 14.12.2022 |
