Natan Rubin
Senior Academic
Planar point sets determine many pairwise crossing segments
We show that any set of n points in general position in the plane determines n1−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.
| Publication language | English |
| Journal | Advances in Mathematics |
| Volume | 386 |
| Publication status | Published - 06.08.2021 |
| Article Number | 107779 |
Keywords
Avoiding sets
Crossing families
Epsilon-nets
Geometric graphs
Intersection graphs
Partial orders
ASJC Scopus subject areas
General Mathematics
