With the usual euclidean distance, i can't figure out how to solve this... I tried to draw the equality case, and then adding another point at one of the distances already in but of course couldn't find any correct placement


2 Answers 2


It is enough to apply the Erdos-Szekeres theorem.

The lines joining two points are finite, so up to rotations we may assume that our points have distinct abscissas.

Assume that we have $M=(n+1)^2+1$ points in the plane $P_1,P_2,\ldots,P_M$, labeled in such a way that $i<j$ implies that the abscissa of $P_i$ is less than the abscissa of $P_j$.

Let $y_1,y_2,\ldots,y_M$ the sequence of the ordinates of $P_1,P_2,\ldots,P_M$. By Erdos-Szekeres this sequence admits a weakly monotonic subsequence $y_{\sigma(1)},y_{\sigma(2)},\ldots,y_{\sigma(n+2)}$, so by considering the distances between $P_{\sigma(1)}$ and $P_{\sigma(2)},\ldots,P_{\sigma(n+2)}$ we have at least $n+1$ different pairwise distances.


Let $g(N)$ denote the minimal number of distinct distances between $N$ points in the plane. In his 1946 paper, Erdős proved the estimates $$\sqrt{N-3/4}-1/2\leq g(N)\leq c N/\sqrt{\log N}.$$ The lower bound is essentially the question of the OP.

After a long string of improvements, Larry Guth and Nets Katz proved in 2015 the lower bound $$ g(N) \ge cN/ {\log N} $$ that almost matches Erdos' upper bound. See [1] for more details and references.

[1] https://en.wikipedia.org/wiki/Erd%C5%91s_distinct_distances_problem


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.