The Open Problems Project

Next: Problem 40: The Number of Pointed Pseudotriangulations

Previous: Problem 38: Compatible Triangulations

Problem 39: Distances among Point Sets in \R^2 and \R^3


For a point set P in \R^d, let f_d(P) be the number of unit-distance point pairs: f_d(P) = \left| \{ (u,v) \mid u, v \in P , \, \|u-v\| = 1 \} \right| \; ; and let f_d(n) be the maximum over all sets of n points: f_d(n) = \max_{|P| = n} f_d(P) \; . Further, let g_d(P) denote the number of distinct distances induced by a set of points P: g_d(P) = \left| \{ \|u-v\| \mid u, v \in P \} \right| \; ; and let g_d(n) be the minimum over all sets of n points: g_d(n) = \min_{|P|=n} g_d(P) \; .

Give upper and lower bounds on f_d(n) and g_d(n), particularly for d=2 and d=3.


Paul Erdős [Erd46].



Partial and Related Results

f_2(n) = O(n^{4/3})~ [Szé97], [CEG+90], [SST84], and f_2(n) = \Omega(n^{1+c/\log\log n}) [Erd46]. f_3(n) = O(n^{5/3}) and f_3(n) = \Omega(n^{4/3} \log \log n) [Erd60]. For g_2(n), the best result is that g_2(n) = \Omega(n^{6/7}) [ST01a]. Erdős conjectured that the correct answer here is n/\sqrt{\log n}; this bound is achieved on the grid.


Erdős offered $500 to settle whether f_2(n) < c n^{1+\epsilon} for some c>0 and for each \epsilon>0, and $500 to settle whether g_2(n) = [1+o(1)] cn/\sqrt{\log n}.


[CFG90], pp. 150-1.


combinatorial geometry

Entry Revision History

S. Venkatasubramanian, 12 Feb. 2002.



K. Clarkson, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, and Emo Welzl. Combinatorial complexity bounds for arrangements of curves and spheres. Discrete Comput. Geom., 5:99–160, 1990.


H. P. Croft, K. J. Falconer, and R. K. Guy. Unsolved Problems in Geometry. Springer-Verlag, 1990.


P. Erdős. On sets of distances of n points. Amer. Math. Monthly, 53:248–250, 1946.


P. Erdős. On sets of distances of n points in Euclidean space. Publications Mathematical Institute of Hungarian Academy of Sciences, 5:165–169, 1960.


L. A. Székely. Crossing numbers and hard Erdős problems in discrete geometry. Combinatorics, Probability and Computing, 6:353–358, 1997.


J. Spencer, E. Szemerédi, and W. T. Trotter. Unit distances in the Euclidean plane. In B. Bollobás, editor, Graph Theory and Combinatorics, pages 293–303. Academic Press, New York, NY, 1984.


J. Solymosi and Cs. D. Tóth. Distinct distances in the plane. Discrete Comput. Geom., 25(4):629–634, 2001.