2022/01/01 by Timothy M. Chan, Da Wei Zheng · 1 citation
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Algorithms and Data Compression #Combinatorics #Mathematics #Dimension (graph theory) #Binary logarithm #Deterministic algorithm #Star (game theory) #Upper and lower bounds #Intersection (aeronautics) #Line (geometry) #Range (aeronautics) #Discrete mathematics #Algorithm #Geometry #Mathematical analysis
paper · doi:10.1137/1.9781611977073.10
openalex created_date 2021/11/22 · openalex publication_date 2022/01/01 · openalex updated_date 2026/08/05
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 Matoušek. 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.