TY - GEN

T1 - Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees

AU - Chan, Timothy M.

AU - Zheng, Da Wei

N1 - Funding Information:
∗Department of Computer Science, University of Illinois at Urbana-Champaign, {tmc,dwzheng2}@illinois.edu. Work supported by NSF Grant CCF-1814026. 1First posed by John Hopcroft in the early 1980s. 2Note that the number of incidences is known to be Θ(n4/3) in the worst case—this is the well-known Szémeredi–Trotter Theorem [59], with lower bound construction provided by Erdös. So, Ω(n4/3) is a trivial lower bound on the time complexity for the “report all” version of Hopcroft’s problem.
Publisher Copyright:
Copyright © 2022 by SIAM Unauthorized reproduction of this article is prohibited.

PY - 2022

Y1 - 2022

N2 - 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(n4=3) time, which matches the conjectured lower bound and improves the best previous time bound of n4=32O(log n) obtained almost 30 years ago by Matousek. We describe two interesting and different ways to achieve the result: the first is randomized and uses a new 2D 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 (1976). The second approach extends to any constant dimension. Many consequences follow from these new ideas: for example, we obtain an O(n4=3)-time algorithm for line segment intersection counting in the plane, O(n4=3)-time randomized algorithms for 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(n4=3) preprocessing time and space and O(n1=3) query time.

AB - 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(n4=3) time, which matches the conjectured lower bound and improves the best previous time bound of n4=32O(log n) obtained almost 30 years ago by Matousek. We describe two interesting and different ways to achieve the result: the first is randomized and uses a new 2D 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 (1976). The second approach extends to any constant dimension. Many consequences follow from these new ideas: for example, we obtain an O(n4=3)-time algorithm for line segment intersection counting in the plane, O(n4=3)-time randomized algorithms for 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(n4=3) preprocessing time and space and O(n1=3) query time.

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

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

M3 - Conference contribution

AN - SCOPUS:85129044194

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 190

EP - 210

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

PB - Association for Computing Machinery

T2 - 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

Y2 - 9 January 2022 through 12 January 2022

ER -