On Constant Factors in Comparison-Based Geometric Algorithms and Data Structures

Algorithms;data structures;computational geometry;Computer Science

Lee, Patrick

University of Waterloo

关键词: Algorithms;    data structures;    computational geometry;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/8783/3/Lee_Patrick.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Many standard problems in computational geometry have been solved asymptotically optimally as far as comparison-based algorithms are concerned, but there has been little work focusing on improving the constant factors hidden in big-Oh bounds on the number of comparisons needed. In this thesis, we consider orthogonal-type problems and present a number of results that achieve optimality in the constant factors of the leading terms, including:- An output-sensitive algorithm that computes the maxima for a set of n points in two dimensions using 1n log(h) + O(n sqrt(log(h))) comparisons, where h is the size of the output.- A randomized algorithm that computes the maxima in three dimensions that uses 1n log(n) + O(n sqrt(log(n))) expected number of comparisons.- A randomized output-sensitive algorithm that computes the maxima in three dimensions that uses 1n log(h) + O(n log^(2/3)(h)) expected number of comparisons, where h is the size of the output.- An output-sensitive algorithm that computes the convex hull for a set of n points in two dimensions using 1n log(h) + O(n sqrt(log(h))) comparisons and O(n sqrt(log(h))) sidedness tests, where h is the size of the output.- A randomized algorithm for detecting whether of a set of n horizontal and vertical line segments in the plane intersect that uses 1n log(n) +O(n sqrt(log(n))) expected number of comparisons.- A data structure for point location among n axis-aligned disjoint boxes in three dimensions that answers queries using at most (3/2)log(n)+ O(log(log(n))) comparisons.The data structure can be extended to higher dimensions and uses at most (d/2)log(n)+ O(log(log(n))) comparisons.- A data structure for point location among n axis-aligned disjoint boxes that form a space-filling subdivision in three dimensions that answers queries using at most (4/3)log(n)+ O(sqrt(log(n))) comparisons.The data structure can be extended to higher dimensions and uses at most ((d+1)/3)log(n)+ O(sqrt(log(n))) comparisons.Our algorithms and data structures use a variety of techniques, including Seidel and Adamy;;s planar point location method, weighted binary search, and height-optimal BSP trees.