Erdős distinct distances problem
E554301
The Erdős distinct distances problem is a famous question in combinatorial geometry that asks for the minimum number of distinct distances determined by a given number of points in the plane.
Statements (41)
| Predicate | Object |
|---|---|
| instanceOf |
mathematical problem
ⓘ
problem in combinatorial geometry ⓘ |
| alsoKnownAs | distinct distances problem NERFINISHED ⓘ |
| asksFor | minimum number of distinct distances determined by n points in the plane ⓘ |
| asymptoticForm | number of distinct distances is at least on the order of n / log n ⓘ |
| breakthroughMethod |
incidence geometry
ⓘ
polynomial method ⓘ |
| breakthroughYear | 2010 ⓘ |
| concerns | extremal configurations of points in the plane ⓘ |
| conjecturedOrderOriginally | n / sqrt(log n) ⓘ |
| difficulty | longstanding and hard problem in discrete geometry ⓘ |
| domain | Euclidean plane ⓘ |
| field |
combinatorial geometry
ⓘ
combinatorics ⓘ discrete geometry ⓘ |
| generalization |
distinct distances in higher dimensions
ⓘ
distinct distances in other metric spaces ⓘ |
| improvedLowerBound | c·n / log n ⓘ |
| improvedLowerBoundProvedBy | Larry Guth and Nets Hawk Katz NERFINISHED ⓘ |
| improvedLowerBoundYear | 2010 ⓘ |
| influenced |
applications of the polynomial method in combinatorics
ⓘ
development of incidence geometry ⓘ |
| involves | pairwise distances between points ⓘ |
| mainQuestion | Given n points in the plane, what is the minimum possible number of distinct pairwise distances? ⓘ |
| majorBreakthroughBy |
Larry Guth
NERFINISHED
ⓘ
Nets Hawk Katz NERFINISHED ⓘ |
| namedAfter | Paul Erdős NERFINISHED ⓘ |
| openAspect |
exact asymptotic constant in the lower bound
ⓘ
tight bound for all n ⓘ |
| originalLowerBound | c·n^{1/2} ⓘ |
| originalLowerBoundProposedBy | Paul Erdős NERFINISHED ⓘ |
| originalUpperBoundConstruction | n / sqrt(log n) ⓘ |
| originalUpperBoundConstructionBy | Paul Erdős NERFINISHED ⓘ |
| posedBy | Paul Erdős NERFINISHED ⓘ |
| relatedTo |
Szemerédi–Trotter theorem
NERFINISHED
ⓘ
incidence bounds between points and lines ⓘ polynomial partitioning technique ⓘ |
| statusBefore2010s | major open problem in combinatorial geometry ⓘ |
| typicalNotation | f(n) for the minimum number of distinct distances ⓘ |
| variable | n points in the plane ⓘ |
| yearPosed | 1946 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.