Problem Statement
Let $t(n)$ be the minimum number of points in $\{1,\ldots,n\}^2$ such that the $\binom{t}{2}$ lines determined by these points cover all points in $\{1,\ldots,n\}^2$.
Estimate $t(n)$. In particular, is it true that $t(n)=o(n)$?
Estimate $t(n)$. In particular, is it true that $t(n)=o(n)$?
Categories:
Geometry
Progress
A problem of Erdős and Purdy, who proved $t(n) \gg n^{2/3}$.Resolved by Alon [Al91] who proved $t(n) \ll n^{2/3}\log n$.
Source: erdosproblems.com/798 | Last verified: January 16, 2026