TY - JOUR

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

AU - Chan, Timothy M.

AU - Lee, Patrick

N1 - Funding Information:
A preliminary version of this paper has appeared in Proc. 30th ACM Sympos. Comput. Geom., pp. 40–49, 2014. This work was supported by NSERC; part of the work was done during the first author’s visit to the Department of Computer Science and Engineering, Hong Kong University of Science and Technology.
Publisher Copyright:
© 2015, Springer Science+Business Media New York.

PY - 2015/4/1

Y1 - 2015/4/1

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

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

KW - Binary space partition

KW - Comparison-based algorithms

KW - Convex hull

KW - Line segment intersection

KW - Maxima

KW - Point location

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

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

U2 - 10.1007/s00454-015-9677-y

DO - 10.1007/s00454-015-9677-y

M3 - Article

AN - SCOPUS:84937764208

SN - 0179-5376

VL - 53

SP - 489

EP - 513

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 3

ER -