DIMACS TR: 94-55

Lines, Line-point Incidences and Crossing Families in Dense Sets



Author: Pavel Valtr

ABSTRACT

Let ${\cal P}$ be a set of $n$ points in the plane. We say that ${\cal P}$ is {\it dense} if the ratio between the maximum and the minimum distance in ${\cal P}$ is of order $O(\sqrt n)$. A set $C$ of line segments in the plane is called {\it a crossing family} if the relative interiors of any two line segments of $C$ intersect. Vertices of line segments of a crossing family $C$ are called {\it vertices of $C$}. It is known that for any set ${\cal P}$ of $n$ points in general position in the plane there is a crossing family of size $\Omega(\sqrt n)$ with vertices in ${\cal P}$. In this paper we show that if ${\cal P}$ is dense then there is a crossing family of almost linear size with vertices in ${\cal P}$.

The above result is related to well-known results of Beck and of Szemer\' edi and Trotter. Beck proved that any set ${\cal P}$ of $n$ points in the plane, not most of them on a line, determines at least $\Omega(n^2)$ different lines. Szemer\' edi and Trotter proved that if ${\cal P}$ is a set of $n$ points and ${\cal L}$ is a set of $m$ lines then there are at most $O(m^{2/3}n^{2/3}+m+n)$ incidences between points of ${\cal P}$ and lines of ${\cal L}$. We study whether or not the bounds shown by Beck and by Szemer\' edi and Trotter hold for any dense set ${\cal P}$ even if the notion of incidence is extended so that a point is considered to be incident to a line $l$ if it lies in a small neighborhood of $l$. In the first case we get very close to the conjectured bound $\Omega(n^2)$. In the second case we obtain a bound of order $O(\min\{m^{3/4}n^{5/8}\log^{1/4} n,n\sqrt m\})$.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-55.ps

DIMACS Home Page