City Research Online

Abstract

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 log3 n) 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 ρ. 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/ρ)) time with high probability.
3. Define dvio 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 dvio) 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.

Publication Type:	Conference or Workshop Item (Paper)
Additional Information:	© Sergio Cabello, Timothy M. Chan and Panos Giannopoulos; licensed under Creative Commons License CC-BY 4.0
Publisher Keywords:	Delaunay Triangulation, Minimum Spanning Tree, Algorithms with Predictions
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments:	School of Science & Technology School of Science & Technology > Department of Computer Science
SWORD Depositor:	Symplectic Administrator

Export

Downloads