DocumentCode :
2913759
Title :
Point Location in o(log n) Time, Voronoi Diagrams in o(n log n) Time, and Other Transdichotomous Results in Computational Geometry
Author :
Chan, Timothy M.
Author_Institution :
Sch. of Comput. Sci., Waterloo Univ., Ont.
fYear :
2006
fDate :
Oct. 2006
Firstpage :
333
Lastpage :
344
Abstract :
Given n points in the plane with integer coordinates bounded by U les 2w, we show that the Voronoi diagram can be constructed in O(min {n log n/ log log n, n(radic(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 Omega(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, radic(log U)}) time with linear space. Higher-dimensional extensions and applications are also mentioned in the paper
Keywords :
algebra; computational geometry; decision trees; randomised algorithms; set theory; Euclidean minimum spanning tree; Voronoi diagrams; algebraic decision tree; computational geometry; planar point set; point location query; randomized algorithm; Computational geometry; Computational modeling; Computer science; Costs; Data structures; Euclidean distance; Polynomials; Read-write memory; Sorting; Tree graphs;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 2006. FOCS '06. 47th Annual IEEE Symposium on
Conference_Location :
Berkeley, CA
ISSN :
0272-5428
Print_ISBN :
0-7695-2720-5
Type :
conf
DOI :
10.1109/FOCS.2006.62
Filename :
4031369
Link To Document :
بازگشت