City Research Online

Delaunay Triangulation and Convex Polygons with Predictions

Cabello, S. & Giannopoulos, P. ORCID: 0000-0002-6261-1961 (2024). Delaunay Triangulation and Convex Polygons with Predictions. Paper presented at the 40th European Workshop on Computational Geometry, 13-15 Mar 2024, Ioannina, Greece.


We show that given a triangulation T of a set P of n points in the plane, the Delaunay triangulation DT(P) of P can be built in O(n + k log4 k) time, where k is the number of edges of DT(P) not present in T. We also show that several problems about convex polygons can be solved in O(log k) time, when the vertices of the polygons are given in an array and we are given a pointer to vertices that in the array are at distance at most k from the vertices defining the solution.

Publication Type: Conference or Workshop Item (Paper)
Subjects: G Geography. Anthropology. Recreation > GA Mathematical geography. Cartography
Q Science > QA Mathematics
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Science & Technology
School of Science & Technology > Computer Science
SWORD Depositor:
[thumbnail of main.pdf]
Text - Pre-print
Download (722kB) | Preview


Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email


Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login