Point sets with distinct distances (Q1900187)

This paper is concerned with the problem of estimating \(f_d (n)\), the maximum cardinality of a subset of the \(n^d - \text{grid} \{1,2, \dots, n\}^d\) with distinct mutual distances. Improving results of \textit{P. Erdös} and \textit{R. K. Guy} [Elemente Math. 25, 121-123 (1970; Zbl 0222.10053)] it is proved that \(f_2(n)\geq cn^{2/3}\) and, for \(d\geq 3\), \(f_d(n)\geq c_dn^{2/3}(\ln n)^{1/3}\). Furthermore, any set of \(n\) points in the plane contains a subset with distinct mutual distances of size \(c_1 n^{1/4}\) and for point sets in general position (i.e., no three collinear) of size \(c_2 n^{1/3}\). Finally, an efficient algorithm is given for finding a subset of a given set with desired properties (for example, with distinct distances) of size guaranteed by the probabilistic method.