REAL

Planar point sets determine many pairwise crossing segments

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

[img]
Preview
Text
1904.08845v1.pdf

Download (485kB) | Preview

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 Edit Item