Given n points in the plane, what is the maximum number of pairs at distance exactly 1? A fundamental question in combinatorial geometry that remains open after 75 years.
Let u(n) be the maximum number of unit distances among n points
in the plane. What is the true order of growth of u(n)?
Current bounds: n^{1+c/log log n} ≤ u(n) ≤ O(n^{4/3})
A unit distance is simply a pair of points that are exactly distance 1 apart. If you think of points as dots on paper and draw a line between two that are exactly 1 unit apart, that line represents a unit distance.
The unit distance problem sits at the heart of combinatorial geometry, a field that studies how geometric constraints limit combinatorial possibilities. It connects to:
Click to place points. Green lines connect points at unit distance. Can you maximize the number of unit distances?
To prove a lower bound on u(n), we need to exhibit point configurations with many unit distances. The best constructions come from lattice structures.
In the triangular (hexagonal) lattice, each interior point has exactly 6 neighbors at unit distance. This is the maximum possible by a classical packing argument: you cannot fit more than 6 non-overlapping unit circles around a point.
However, the best asymptotic constructions use more sophisticated number-theoretic ideas to achieve u(n) = n^{1+c/log log n} for some constant c > 0.
Using ShinkaEvolve (evolutionary code optimization) with gemini-3-pro-preview, we discovered an improved greedy construction algorithm. Instead of filling a rectangular region of the triangular lattice, the evolved algorithm grows a compact "blob" shape by iteratively adding the lattice point that maximizes unit-distance connections.
| n (points) | Unit Distances | Ratio u(n)/n |
|---|---|---|
| 25 | 57 | 2.28 |
| 50 | 133 | 2.667 |
| 100 | 265 | 2.65 |
The evolution converged on lattice-based approaches with local search optimization. For n=50, the best configuration achieves 133 unit distances (ratio 2.667). The theoretical upper bound O(n^{4/3}) ≈ 185 for n=50. Try it using the "Evolved Greedy" button above!
The chart below shows the theoretical bounds compared to our computational results. The gap between lower and upper bounds represents the open problem.
The gap between n^{1+c/log log n} and n^{4/3} is enormous. For n = 10^6, the lower bound gives roughly n^{1.05} while the upper bound allows n^{1.33}. Closing this gap is worth $500.
Erdos believed the true answer is closer to the lower bound: that u(n) grows only slightly faster than linear. Any improvement to either bound would be a significant breakthrough.
The upper bound u(n) = O(n^{4/3}) comes from a beautiful connection to incidence geometry - the study of how points and curves can intersect.
Each incidence (orange) is where a point lies on a line. The theorem bounds the total count.
The key insight is that each unit distance corresponds to an incidence between a point P and a unit circle centered at another point Q. If we count how many times points lie on unit circles centered at other points, we are counting unit distances.
Point Q at unit distance from P lies on the unit circle centered at P. Each such incidence is a unit distance.
Using a generalization of Szemeredi-Trotter to circles (proved by Spencer, Szemeredi, and Trotter), one obtains:
The Szemeredi-Trotter bound for lines is tight - there exist configurations achieving the bound. However, the situation for unit circles is different. The constraint that all circles have the same radius should help, but we don't know how to exploit it.
The unit distance problem belongs to a family of extremal problems in combinatorial geometry. Related questions include:
The distinct distances problem (Erdős Problem #89) asks: what is the minimum number of distinct distances determined by n points? Erdős conjectured this minimum is Ω(n/√log n), achieved by the integer lattice.
This was a major breakthrough using algebraic geometry techniques (the polynomial method). The connection to unit distances is deep: if we could maximize repeated distances, we would minimize distinct distances.
Integer lattice: many repeated distances (colored by type) but still Ω(n/√log n) distinct values.
In d dimensions (d ≥ 4), the unit distance problem is essentially solved. The maximum is Theta(n^2) in 4D and higher, achieved by placing points on a 2-dimensional sphere. The cases d = 2 and d = 3 remain the most mysterious.