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

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 paper, we consider orthogonal-type problems and present a number of results that achieve optimality in the constant factors of the leading terms, includingan algorithm for the 2D maxima problem that uses (Formula presented.) comparisons, where (Formula presented.) denotes the output size;a randomized algorithm for the 3D maxima problem that uses (Formula presented.) expected number of comparisons;a randomized algorithm for detecting intersections among a set of orthogonal line segments that uses (Formula presented.) expected number of comparisons;a data structure for point location among 3D disjoint axis-parallel boxes that can answer queries in (Formula presented.) comparisons;a data structure for point location in a 3D box subdivision that can answer queries in (Formula presented.) comparisons. Some of the results can be adapted to solve nonorthogonal problems, such as 2D convex hulls and general line segment intersection. 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.