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.