Planar point sets determine many pairwise crossing segments
János Pach, Natan Rubin, Gábor Tardos · Advances in Mathematics · 2019
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, Ω ( n ) , was proved more than 25 years ago by Aronov, Erdős, Goddard, Kleitman, Klugerman, Pach, and Schulman. Our proof is fully constructive, and extends to dense geometric graphs.