20.500.12556/RUL-179802 Delaunay triangulations with predictions 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. Delaunay triangulation minimum spanning tree algorithms with predictions true false true Angleški jezik Angleški jezik Članek v reviji 2026-02-25 08:41:05 2026-02-25 08:41:09 2026-02-26 04:31:32 0000-00-00 00:00:00 2026 0 0 Str. 31:1-31:23 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004:519.17 1868-8969 10.4230/LIPIcs.ITCS.2026.31 269543427 269488387 LIPIcs.ITCS.2026.31.pdf LIPIcs.ITCS.2026.31.pdf 1 248C52A0DC5F60A8967B00825B71A349 cb2ef03fb110fc1ceb2fcb6a251927605e10a3c5bf0e6068c0eda8239a77698e f9e66584-121d-11f1-a1ba-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=228636 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.31 0 43134c6c-121e-11f1-a1ba-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=228637 Fakulteta za matematiko in fiziko 0 0 0