Problem Statement
Let $A\subset \mathbb{R}^2$ be a set of $n$ points with no three on a line. Does $A$ determine at least $\lfloor n/2\rfloor$ distinct distances? In fact, must there exist a single point from which there are at least $\lfloor n/2\rfloor$ distinct distances?
Categories:
Geometry Distances
Progress
A conjecture of Szemerédi, who proved this with $n/2$ replaced by $n/3$. More generally, Szemerédi gave a simple proof that if there are no $k$ points on a line then some point determines $\gg n/k$ distinct distances (a weak inverse result to the distinct distance problem [89]).This is a stronger form of [93]. The second question is a stronger form of [982].
Szemerédi's proof is unpublished, but given in [Er75f].
In [Er75f] Erdős asks whether, given $n$ points in $\mathbb{R}^3$ with no three on a line, do they determine $\gg n$ distances? Altman proved the answer is yes if the points form the vertices of a convex polyhedron (see [660] for a stronger form of this), and Szemerédi proved the answer is yes if there are no four points on a plane.
The stronger second question has been answered negatively by Xichuan in the comments, who gave a set of $42$ points in $\mathbb{R}^2$, with no three on a line, such that each point determines only $20$ distinct distances.
Source: erdosproblems.com/1082 | Last verified: January 19, 2026