Planar Point Sets Determine Many Pairwise Crossing Segments

Abstract

We show that any set of $n$ points in general position in the plane determines $n^{1-o(1)}$ pairwise crossing segments. The best previously known lower bound, $\Omega \left(\sqrt{n}\right)$, was proved more than 25 years ago by Aronov, Erd\H os, Goddard, Kleitman, Klugerman, Pach, and Schulman. Our proof is fully constructive, and extends to dense geometric graphs.

A preliminary version to appear in the proceedings of STOC 2019