Hopcroft's Problem, Log∗Shaving, Two-dimensional Fractional Cascading, and Decision Trees

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 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 query time.