Pach, János and Rubin, Natan and Tardos, Gábor (2019) Planar point sets determine many pairwise crossing segments. In: STOC 2019 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery (ACM), New York, pp. 11581166. ISBN 9781450367059

Text
1904.08845v1.pdf Download (485kB)  Preview 
Official URL: http://doi.org/10.1145/3313276.3316328
Abstract
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. © 2019 Association for Computing Machinery.
Item Type:  Book Section 

Uncontrolled Keywords:  Computation theory; Extremal combinatorics; Extremal combinatorics; Computational geometry; Computational geometry; Graphic methods; Geometric graphs; Geometric graphs; Crossing edges; Crossing edges; Intersection graphs; Intersection graph; Partial orders; Partial order; Avoiding edges; Comparability graphs; Avoiding edges; Comparability graphs; 
Subjects:  Q Science / természettudomány > QA Mathematics / matematika > QA71 Number theory / számelmélet Q Science / természettudomány > QA Mathematics / matematika > QA73 Geometry / geometria 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  02 Oct 2019 13:24 
Last Modified:  02 Oct 2019 13:24 
URI:  http://real.mtak.hu/id/eprint/101917 
Actions (login required)
Edit Item 