Point location in o(log n) time, Voronoi diagrams in o(n log n) time, and other transdichotomous results in computational geometry

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

Abstract

Given n points in the plane with integer coordinates bounded by U ≤ 2w, we show that the Voronoi diagram can be constructed in O(min{n log n / log log n, n√log U}) expected time by a randomized algorithm on the unit-cost RAM with word size w. Similar results are also obtained for many other fundamental problems in computational geometry, such as constructing the convex hull of a 3-dimensional point set, computing the Euclidean minimum spanning tree of a planar point set, triangulating a polygon with holes, and finding intersections among a set of line segments. These are the first results to beat the Ω(n log n) algebraic-decision-tree lower bounds known for these problems. The results are all derived from a new two-dimensional version of fusion trees that can answer point location queries in O(min{log n / log log n, √log U}) time with linear space. Higher-dimensional extensions and applications are also mentioned in the paper.

Original languageEnglish (US)
Title of host publication47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
Pages333-342
Number of pages10
DOIs
StatePublished - 2006
Externally publishedYes
Event47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006 - Berkeley, CA, United States
Duration: Oct 21 2006Oct 24 2006

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
CountryUnited States
CityBerkeley, CA
Period10/21/0610/24/06

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Point location in o(log n) time, Voronoi diagrams in o(n log n) time, and other transdichotomous results in computational geometry'. Together they form a unique fingerprint.

Cite this