Hopcroft’s Problem, Log* Shaving, Two-dimensional Fractional Cascading, and Decision Trees
Open Access
- 21 June 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 20 (3) , 1-27
Abstract
We revisit Hopcroft’s problem and related fundamental problems about geometric range searching. Given n points and n lines in the plane, we show how to count the number of point-line incidence pairs or the number of point-above-line pairs in O ( n 4/3 ) time, which matches the conjectured lower bound and improves the best previous time bound of \(n^{4/3}2^{O(\log ^*n)}\) obtained almost 30 years ago by Matoušek [ 58 ]. We describe two interesting and different ways to achieve the result: The first is randomized and uses a new two-dimensional version of fractional cascading for arrangements of lines; the second is deterministic and uses decision trees in a manner inspired by the sorting technique of Fredman [42]. The second approach extends to any constant dimension. Many consequences follow from these new ideas: For example, we obtain an O ( n 4/3 )-time algorithm for line segment intersection counting in the plane, O ( n 4/3 )-time randomized algorithms for distance selection in the plane and bichromatic closest pair and Euclidean minimum spanning tree in three or four dimensions, and a randomized data structure for halfplane range counting in the plane with O ( n 4/3 ) preprocessing time and space and \(O(n^{1/3})\) query time.
Keywords
Funding Information
- NSF (CCF-1814026, CCF-2224271)
This publication has 64 references indexed in Scilit:
- Optimal Partition TreesDiscrete & Computational Geometry, 2012
- Subquadratic Algorithms for 3SUMAlgorithmica, 2007
- On a class of O(n2) problems in computational geometryComputational Geometry, 1995
- Approximations and Optimal Geometric Divide-and-ConquerJournal of Computer and System Sciences, 1995
- On computing connected components of line segmentsIEEE Transactions on Computers, 1995
- A pseudo-algorithmic separation of lines from pseudo-linesInformation Processing Letters, 1995
- Algorithms for bichromatic line-segment problems and polyhedral terrainsAlgorithmica, 1994
- Selecting distances in the planeAlgorithmica, 1993
- Reporting points in halfspacesComputational Geometry, 1992
- An optimal algorithm with unknown time complexity for convex matrix searchingInformation Processing Letters, 1990