Delaunay triangulations with predictions

Cabello, Sergio (avtor), Chan, Timothy M. (avtor), Giannopoulos, Panos (avtor)

We investigate algorithms with predictions in computational geometry, specifically focusing on the basic problem of computing 2D Delaunay triangulations. Given a set $P$ of $n$ points in the plane and a triangulation $G$ that serves as a "prediction" of the Delaunay triangulation, we would like to use $G$ to compute the correct Delaunay triangulation $DT(P)$ more quickly when $G$ is "close" to $DT(P)$. We obtain a variety of results of this type, under different deterministic and probabilistic settings, including the following: 1) Define $D$ to be the number of edges in $G$ that are not in $DT(P)$. We present a deterministic algorithm to compute $DT(P)$ from $G$ in $O(n + D\log^3n)$ time, and a randomized algorithm in $O(n+D\log n)$ expected time, the latter of which is optimal in terms of $D$. 2) Let $R$ be a random subset of the edges of $DT(P)$, where each edge is chosen independently with probability $\rho$. Suppose $G$ is any triangulation of $P$ that contains $R$. We present an algorithm to compute $DT(P)$ from $G$ in $O(n\log \log n + n\log(1/\rho))$ time with high probability. 3) Define $d_{\rm vio}$ to be the maximum number of points of $P$ strictly inside the circumcircle of a triangle in $G$ (the number is $0$ if $G$ is equal to $DT(P)$). We present a deterministic algorithm to compute $DT(P)$ from $G$ in $O(n\log^*n + n\log d_{\rm vio})$ time. We also obtain results in similar settings for related problems such as 2D Euclidean minimum spanning trees, and hope that our work will open up a fruitful line of future research.

• Jezik: Angleški jezik
• Ključne besede: Delaunay triangulation, minimum spanning tree, algorithms with predictions
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.08 - Objavljeni znanstveni prispevek na konferenci
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2026
• Št. strani: Str. 31:1-31:23
• PID: 20.500.12556/RUL-179802
• UDK: 004:519.17
• ISSN pri članku: 1868-8969
• DOI: 10.4230/LIPIcs.ITCS.2026.31
• COBISS.SI-ID: 269543427
• Datum objave v RUL: 25.02.2026

Gradivo je del zbornika

• Naslov: 17th Innovations in Theoretical Computer Science Conference
• COBISS.SI-ID: 269488387

Gradivo je del revije

• Naslov: Leibniz international proceedings in informatics
• Skrajšan naslov: Leibniz int. proc. inform.
• Založnik: Schloss Dagstuhl, Leibniz-Zentrum für Informatik
• ISSN: 1868-8969
• COBISS.SI-ID: 523260441

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.