TY - GEN

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

AU - Chan, Timothy M.

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

PY - 2006

Y1 - 2006

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

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

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

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

U2 - 10.1109/FOCS.2006.62

DO - 10.1109/FOCS.2006.62

M3 - Conference contribution

AN - SCOPUS:35348864219

SN - 0769527205

SN - 9780769527208

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 333

EP - 342

BT - 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006

T2 - 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006

Y2 - 21 October 2006 through 24 October 2006

ER -