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 + 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ₕ₈₎ 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ₕ₈₎) 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.