Loading...
conference paper
Planar Point Sets Determine Many Pairwise Crossing Segments
January 1, 2019
Proceedings Of The 51St Annual Acm Sigact Symposium On Theory Of Computing (Stoc '19)
We show that any set of n points in general position in the plane determines n(1-o(1)) pairwise crossing segments. The best previously known lower bound, Omega(root n), was proved more than 25 years ago by Aronov, Erdos, Goddard, Kreitman, Krugerman, Pach, and Schulman. Our proof is fully constructive, and extends to dense geometric graphs.
Type
conference paper
Web of Science ID
WOS:000523199100105
Authors
Publication date
2019-01-01
Publisher
Published in
Proceedings Of The 51St Annual Acm Sigact Symposium On Theory Of Computing (Stoc '19)
ISBN of the book
978-1-4503-6705-9
Publisher place
New York
Series title/Series vol.
Annual ACM Symposium on Theory of Computing
Start page
1158
End page
1166
Peer reviewed
REVIEWED
EPFL units
Event name | Event place | Event date |
Phoenix, AZ | Jun 23-26, 2019 | |
Available on Infoscience
April 22, 2020
Use this identifier to reference this record