Delaunay Triangulations with Predictions

Sergio Cabello, Timothy M. Chan, Panos Giannopoulos · 2026

Read Delaunay Triangulations with Predictions by Sergio Cabello, Timothy M. Chan, Panos Giannopoulos (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-08106.txt.

Introduction

Sergio Cabello, Timothy Chan, and Panos Giannopoulos study Delaunay triangulations with help from predictions. Their 2026 arXiv paper treats a basic task in computational geometry. Given points in the plane, the Delaunay triangulation is a standard mesh with strong shape properties.

The setting adds a predicted triangulation G, a guess at the correct answer. When G lies close to the true triangulation, an algorithm should finish faster than starting cold. The authors ask how to use a good guess without being hurt by a bad one. Their work joins a growing line on algorithms that learn from predictions while keeping firm guarantees.

Catalog record

CREATORSergio Cabello, Timothy M. Chan, Panos Giannopoulos
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-08106

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Delaunay Triangulations with Predictions Sergio Cabello, Timothy M. Chan, Panos Giannopoulos Abstract We investigate algorithms with predictions in computational geometry, specifically focusing on the basic problem of computing 2D Delaunay triangulations. Given a set P P of n n points in the plane and a triangulation G G that serves as a “prediction” of the Delaunay triangulation, we would like to use G G to compute the correct Delaunay triangulation DT ​ ( P ) \textit{DT}(P) more quickly when G G is “close” to DT ​ ( P ) \textit{DT}(P) . We obtain a variety of results of this type, under different deterministic and probabilistic settings, including the following: 1. Define D D to be the number of edges in G G that are not in DT ​ ( P ) \textit{DT}(P) . We present a deterministic algorithm to compute DT ​ ( P ) \textit{DT}(P) from G G in O ⁡ ( n + D ​ log 3 ​ n ) O(n+D\log^{3}n) time, and a randomized algorithm in O ⁡ ( n + D ​ log ⁡ n ) O(n+D\log n) expected time, the latter of which is optimal in terms of D D . 2. Let R R be a random subset of the edges of DT ​ ( P ) \textit{DT}(P) , where each edge is chosen independently with probability ρ \rho . Suppose G G is any triangulation of P P that contains R R . We present an algorithm to compute DT ​ ( P ) \textit{DT}(P) from G G in O ⁡ ( n ​ log ⁡ log ⁡ n + n ​ log ⁡ ( 1 / ρ ) ) O(n\log\log n+n\log(1/\rho)) time with high probability. 3. Define d vio d_{\mbox{\scriptsize\rm vio}} to be the maximum number of points of P P strictly inside the circumcircle of a triangle in G G (the number is 0 if G G is equal to DT ​ ( P ) \textit{DT}(P) ). We present a deterministic algorithm to compute DT ​ ( P ) \textit{DT}(P) from G G in O ⁡ ( n ​ log ∗ ​ n + n ​ log ⁡ d vio ) O(n\log^{*}n+n\log d_{\mbox{\scriptsize\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. 1 Introduction 1.1 Towards computational geometry with predictions Algorithms with predictions have received considerable attention in recent years. Given a problem instance and a prediction for the solution, we would like to devise an algorithm that solves the problem in such a way that the algorithm performs “better” when the prediction is “close” to the correct solution. “Better” may be in terms of running time, or approximation factor (for optimization problems), or competitive ratio (for on-line problems). Different measures of “closeness” may be used depending on the problem, or alternatively we may assume that predictions obey some probabilistic models. The paradigm has been applied to problems in diverse areas, such as scheduling, classical graph problems, resource allocation, mechanism design, facility location, and graph searching to name a few; see the survey in [ 54 ] and the regularly updated online list of papers in [ 2 ] . In contrast, work on algorithms with predictions in computational geometry have been few and far between. The goal of this paper is to promote this direction of research. Primarily, we concentrate on the use of predictions to improve the running time of geometric algorithms. As many fundamental problems in classical computational geometry may be viewed as two- or higher-dimensional generalizations of standard one-dimensional problems like sorting and searching, we start our discussion with the 1D sorting problem. Here, algorithms with predictions are related to the historically well-explored topic of adaptive sorting algorithms [ 34 ] —if we are given a sequence that is already close to sorted, we can sort faster. There are different ways to measure distance to sortedness. For example: • Consider D_{\textrm{inv}} , the number of inversions in the given sequence (i.e., the number of out-of-order pairs). In terms of this parameter, good old insertion-sort runs in O(n+D_{\textrm{inv}}) time and already beats O(n\log n) algorithms when D_{\textrm{inv}}=O(n) . Better algorithms are known running in \Theta(n\log(1+D_{\textrm{inv}}/n)) time, which is optimal in comparison-based models. • Or consider D_{\textrm{rem}} , the minimum number of elements to remove (the “wrong” elements) so that the remaining list is sorted. Here, the optimal time bound is known to be \Theta(n+D_{\textrm{rem}}\log n) . • Or consider D_{\textrm{runs}} , the number of runs (i.e., the number of increasing contiguous subsequence that the input can be partitioned into). Here, the optimal time bound is known to be \Theta(n\log D_{\textrm{runs}}) . Unfortunately, even when D_{\textrm{runs}} is as low as n^{0.1} , it is not possible to beat n\log n under this distance measure. The survey in [ 34 ] gives an extensive background and a (long) list of other parameters that have been considered in the algorithms literature. Adaptive sorting has continued to be studied (some random recent examples include [ 7 , 55 , 4 ] ), and some recent papers [ 6 , 49 ] examine newer models for sorting with predictions. 1.2 The 2D Delaunay triangulation problem Can we obtain similar results for geometric problems in 2D? In this paper, we pick arguably one of the most basic problems in computational geometry to start this study: namely, the computation of the Delaunay triangulation , denoted \textit{DT}(P) , of a set P of n points in the plane [ 29 ] . One way to define \textit{DT}(P) is via the empty circle property : three points p,p^{\prime},p^{\prime\prime}\in P form a Delaunay triangle iff the circumcircle through p,p^{\prime},p^{\prime\prime} does not have any points of P strictly inside. (Throughout this paper, we assume for simplicity that the input is in general position, e.g., no 4 input points are co-circular.) Delaunay triangulations are combinatorially equivalent to Voronoi diagrams (under the Euclidean metric) by duality. (It is a little more convenient to work with Delaunay triangulations than Voronoi diagrams when specifying the prediction G or defining closeness, and so all our results will be stated in terms of the former.) Delaunay triangulations and Voronoi diagrams are among the most ubiquitous geometric structures, with countless applications, and lie at the very core of computational geometry. In the prediction setting, we are given not just the input point set P , but also a triangulation G of P (i.e., a decomposition of the convex hull of P into nonoverlapping triangles, using all the points of P as vertices, but no Steiner points). The goal is to devise an algorithm to compute \textit{DT}(P) faster, when the “distance” between G and \textit{DT}(P) is small. In the traditional setting, several standard textbook algorithms are known for computing the Delaunay triangulation in O(n\log n) time, e.g., via divide-and-conquer, plane sweep, and randomized incremental construction [ 8 , 29 , 5 , 36 ] , which is optimal in the worst case. Without closeness, an arbitrary triangulation G of P still provides some extra information about the input, but not enough to beat n\log n : it is not difficult to see that

Read the complete text