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, including: • an algorithm for the 2D maxima problem that uses n lg h + O(n √lg h) comparisons, where h denotes the output size; • a randomized algorithm for the 3D maxima problem that uses n lg h+O(n lg^2/3 h) expected number of comparisons; • a randomized algorithm for detecting intersections among a set of orthogonal line segments that uses n lg n + O(n √ lg n) expected number of comparisons; • a data structure for point location among 3D disjoint axis-parallel boxes that can answer queries in (3=2) lg n + O(lg lg n) comparisons; • a data structure for point location in a 3D box sub-division that can answer queries in (4/3) lg n+O( √ lg n) 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. Copyright is held by the owner/author(s).