City Research Online

Abstract

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:	Symplectic Administrator

Export

Downloads