Publication

Planar Point Sets Determine Many Pairwise Crossing Segments

János Pach
2019
Conference Papers

Résumé

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.

Source officielle

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Planar Point Sets Determine Many Pairwise Crossing Segments

Chattez avec Graph Search

Approximating the rectilinear crossing number

A Note on Lenses in Arrangements of Pairwise Intersecting Circles in the Plane

Vector-Based 3D Graphic Statics: a framework for the design of spatial structures based on the relation between form and forces