## 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