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 |
| Pages | 1158-1166 |
| Publication status | Published - 23.06.2019 |
Keywords
Avoiding edges
Comparability graphs
Computational geometry
Crossing edges
Extremal combinatorics
Geometric graphs
Intersection graphs
Partial orders
ASJC Scopus subject areas
Software
