Planar point sets with forbidden 4-point patterns and few distinct distances

2024/09/02 by Terence Tao, Tao, Terence
Computer Science · Mathematics · #05B25 #52C10 #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Mathematics #Mathematical Approximation and Integration

paper · pdf · doi:10.48550/arxiv.2409.01343

openalex publication_date 2024/09/02 · openalex created_date 2024/09/29 · openalex updated_date 2026/07/28

Abstract

We show that for any large n, there exists a set of n points in the plane with O(n²/√(log n)) distinct distances, such that any four points in the set determine at least five distinct distances. This answers (in the negative) a question of Erdős. The proof combines an analysis by Dumitrescu of forbidden four-point patterns with an algebraic construction of Thiele and Dumitrescu (to eliminate parallelograms), as well as a randomized transformation of that construction (to eliminate most other forbidden patterns).

Related

• Few distinct distances implies no heavy lines or circles
• Lattice Configurations Determining Few Distances
• On sets with few distinct distances
• On the Erdos distinct distance problem in the plane
• Distinct distances between a collinear set and an arbitrary set of points