Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Planar Point Sets Determine Many Pairwise Crossing Segments
 
conference paper

Planar Point Sets Determine Many Pairwise Crossing Segments

Pach, Janos  
•
Rubin, Natan
•
Tardos, Gabor
January 1, 2019
Proceedings Of The 51St Annual Acm Sigact Symposium On Theory Of Computing (Stoc '19)
51st Annual ACM SIGACT Symposium on Theory of Computing (STOC)

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.

  • Details
  • Metrics
Type
conference paper
DOI
10.1145/3313276.3316328
Web of Science ID

WOS:000523199100105

Author(s)
Pach, Janos  
Rubin, Natan
Tardos, Gabor
Date Issued

2019-01-01

Publisher

ASSOC COMPUTING MACHINERY

Publisher place

New York

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

Series title/Series vol.

Annual ACM Symposium on Theory of Computing

Start page

1158

End page

1166

Subjects

Computer Science, Theory & Methods

•

Computer Science

•

computational geometry

•

geometric graphs

•

intersection graphs

•

crossing edges

•

avoiding edges

•

partial orders

•

comparability graphs

•

extremal combinatorics

•

string graphs

•

number

•

patterns

•

bounds

•

edges

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Event nameEvent placeEvent date
51st Annual ACM SIGACT Symposium on Theory of Computing (STOC)

Phoenix, AZ

Jun 23-26, 2019

Available on Infoscience
April 22, 2020
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/168313
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés