  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\v{s}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(n^{4/3})$-time algorithm for line segment intersection counting in the
plane, $O(n^{4/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(n^{4/3})$
preprocessing time and space and $O(n^{1/3})$ query time.
