Publication

Planar Point Sets Determine Many Pairwise Crossing Segments

János Pach
2019
Conference Papers

Abstract

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.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Planar Point Sets Determine Many Pairwise Crossing Segments

Chat with 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