Point Sets with Distinct Distances
Torsten Thiele (joint work with Hanno Lefmann)
Fachbereich Mathematik und Informatik
Freie Universität Berlin
email: thiele@math.fu-berlin.de
Report B 94-16
August 94
Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-94-16.ps.gz
For positive integers $d$ and $ n$ let $f_{d}(n)$ denote the maximum cardinality
of a subset of the $n^{d}$-grid $\{1, 2, \ldots, n\}^{d}$
with distinct mutual euclidean distances. Improving earlier
results of Erd\H{o}s and Guy, it will be shown
that $f_{2}(n) \geq c \cdot n^{2/3}$ and, for $d \geq 3$, that
$f_{d}(n) \geq c_{d} \cdot n^{2/3} \cdot (\ln n)^{1/3}$, where $c, c_{d} > 0$ are constants.
Also improvements of lower bounds of Erd\H{o}s and Alon on the size of
Sidon-sets in $\{ 1^{2}, 2^{2}, \ldots , n^{2} \}$ are given.
Furthermore, it will be proven that any set of $n$ points in the plane
contains a subset with distinct mutual distances of size $c_1 \cdot n^{1/4}$,
and for point sets in general position, i.e.\ no three points on a line,
of size $c_2 \cdot n^{1/3}$ with constants $c_1, c_2 >0$. To do so, it will
be shown
that for $n$ points in $\R^{2}$ with distinct distances $d_{1}, d_{2},
\ldots , d_{t}$, where $d_{i}$ has multiplicity $m_{i}$, one has
$\sum_{i=1}^{t} m_{i}^{2} \leq c\cdot n^{3.25}$ for a positive constant $c$. If the $n$ points
are in general position, then we prove $\sum_{i=1}^{t} m_{i}^{2} \leq c
\cdot n^{3}$
for a positive constant $c$ and this bound is tight. This confirms a conjecture of Erd\H{o}s and Fishburn.
Moreover, we give an efficient sequential algorithm for finding
a subset of a given set with the desired properties, for example with
distinct distances, of size as guaranteed by the
probabilistic method under a more general setting.