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

Timothy M. Chan, Da Wei Zheng

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 poin…