TY - GEN

T1 - On constant factors in comparison-based geometric algorithms and data structures

AU - Chan, Timothy M.

AU - Lee, Patrick

PY - 2014

Y1 - 2014

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, 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 lg2/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).

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, 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 lg2/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).

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=84904412792&partnerID=8YFLogxK

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

U2 - 10.1145/2582112.2582166

DO - 10.1145/2582112.2582166

M3 - Conference contribution

AN - SCOPUS:84904412792

SN - 9781450325943

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 40

EP - 49

BT - Proceedings of the 30th Annual Symposium on Computational Geometry, SoCG 2014

PB - Association for Computing Machinery

T2 - 30th Annual Symposium on Computational Geometry, SoCG 2014

Y2 - 8 June 2014 through 11 June 2014

ER -