2026-07-20T14:44:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25318 2026-03-19T13:03:26Z ddc:004 open_access

Delaunay Triangulations with Predictions Cabello, Sergio Chan, Timothy M. Giannopoulos, Panos Delaunay Triangulation Minimum Spanning Tree Algorithms 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 + Dlog³ n) time, and a randomized algorithm in O(n+Dlog 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 ρ. Suppose G is any triangulation of P that contains R. We present an algorithm to compute DT(P) from G in O(nlog log n + nlog(1/ρ)) time with high probability. 3) Define d_{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(nlog^*n + nlog d_{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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sergio Cabello and Timothy M. Chan and Panos Giannopoulos 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.31 urn:nbn:de:0030-drops-253186 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.31 eng https://creativecommons.org/licenses/by/4.0/legalcode