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

Timothy M. Chan, Mihai Pǎtraşcu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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).

Original languageEnglish (US)
Title of host publicationSTOC'07
Subtitle of host publicationProceedings of the 39th Annual ACM Symposium on Theory of Computing
Pages31-39
Number of pages9
DOIs
StatePublished - 2007
Externally publishedYes
EventSTOC'07: 39th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
Duration: Jun 11 2007Jun 13 2007

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

OtherSTOC'07: 39th Annual ACM Symposium on Theory of Computing
CountryUnited States
CitySan Diego, CA
Period6/11/076/13/07

Keywords

  • Computational geometry
  • Convex hulls
  • Point location
  • Segment intersection
  • Sorting
  • Word-RAM algorithms

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Voronoi diagrams in n 2<sup>o(√lg lg n)</sup> time'. Together they form a unique fingerprint.

Cite this