TY - GEN

T1 - Voronoi diagrams in n 2o(√lg lg n) time

AU - Chan, Timothy M.

AU - Pǎtraşcu, Mihai

N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.

PY - 2007

Y1 - 2007

N2 - We reexamine fundamental problems from computational geometry in theallword RAM model, where input coordinates are integers that fit in a machine word. We develop a new algorithm for offline point location, a two-dimensional analog of sorting where one needs to order points with respect to segments. This result implies, for example, that the Voronoi diagram of n points in the plane can be constructed in (randomized) time n 2O( lg lg n). Similar bounds hold for numerous other geometric problems, such as three-dimensional convex hulls, planar Euclidean minimum spanning trees, line segment intersection, and triangulation of non-simple polygons. In FOCS'06, we developed a data structure for online point location, which implied a bound of O(n (lg n)/(lg lg n) for Voronoi diagrams and the other problems. Our current bounds are dramatically better, and a convincing improvement over the classic O(n lg n) algorithms. As in the field of integer sorting, the main challenge is to find ways to manipulate information, while avoiding the online problem (in that case, predecessor search).

AB - We reexamine fundamental problems from computational geometry in theallword RAM model, where input coordinates are integers that fit in a machine word. We develop a new algorithm for offline point location, a two-dimensional analog of sorting where one needs to order points with respect to segments. This result implies, for example, that the Voronoi diagram of n points in the plane can be constructed in (randomized) time n 2O( lg lg n). Similar bounds hold for numerous other geometric problems, such as three-dimensional convex hulls, planar Euclidean minimum spanning trees, line segment intersection, and triangulation of non-simple polygons. In FOCS'06, we developed a data structure for online point location, which implied a bound of O(n (lg n)/(lg lg n) for Voronoi diagrams and the other problems. Our current bounds are dramatically better, and a convincing improvement over the classic O(n lg n) algorithms. As in the field of integer sorting, the main challenge is to find ways to manipulate information, while avoiding the online problem (in that case, predecessor search).

KW - Computational geometry

KW - Convex hulls

KW - Point location

KW - Segment intersection

KW - Sorting

KW - Word-RAM algorithms

UR - http://www.scopus.com/inward/record.url?scp=35448940905&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35448940905&partnerID=8YFLogxK

U2 - 10.1145/1250790.1250796

DO - 10.1145/1250790.1250796

M3 - Conference contribution

AN - SCOPUS:35448940905

SN - 1595936319

SN - 9781595936318

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 31

EP - 39

BT - STOC'07

T2 - STOC'07: 39th Annual ACM Symposium on Theory of Computing

Y2 - 11 June 2007 through 13 June 2007

ER -