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. 1158-1166. 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 |
