Spanning Trees of Low Stabbing Number
Theorem 1: For every set S of n points in the plane there exists
a spanning T, whose vertices are the points of S and such that
any line crosses at most 4*sqrt(n) + o(sqrt(n)) edges of T.
I will present a proof of Theorem 1, which was originally proven
in a more general setting by Chazelle and Welzl (1989). This
result, and the proof techniques it uses, have found several
applications in geometric discrepancy theory, combinatorial
geometry, geometric range searching, and algorithms for linear
programming.