Few distinct distances implies no heavy lines or circles

DOI10.1007/S00493-014-3180-6zbMATH Open1399.52034arXiv1308.5620OpenAlexW2103821238MaRDI QIDQ1701352FDOQ1701352

Authors: Adam Sheffer, J. Zahl, Frank de Zeeuw 

Publication date: 22 February 2018

Published in: Combinatorica (Search for Journal in Brave)

Abstract: We study the structure of planar point sets that determine a small number of distinct distances. Specifically, we show that if a set P of n points determines o(n) distinct distances, then no line contains Omega(n^{7/8}) points of P and no circle contains Omega(n^{5/6}) points of P. We rely on the bipartite and partial variant of the Elekes-Sharir framework that was presented by Sharir, Sheffer, and Solymosi in cite{SSS13}. For the case of lines we combine this framework with a theorem from additive combinatorics, and for the case of circles we combine it with some basic algebraic geometry and a recent incidence bound for plane algebraic curves by Wang, Yang, and Zhang cite{WYZ13}. A significant difference between our approach and that of cite{SSS13} (and other recent extensions) is that, instead of dealing with distances between two point sets that are restricted to one-dimensional curves, we consider distances between one set that is restricted to a curve and one set with no restrictions on it.

Full work available at URL: https://arxiv.org/abs/1308.5620

Recommendations

• Sets with few distinct distances do not have heavy lines
• Distinct distances between points and lines
• Distinct distances on algebraic curves in the plane
• Distinct Distances on Algebraic Curves in the Plane
• Distinct distances on two lines

zbMATH Keywords

distinct distancespoint setsheavy lines

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10)

Cites Work

• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Convexity and sumsets
• Convexity and a sum-product type estimate
• On the Erdős distinct distances problem in the plane
• On the Number of Incidences Between Points and Curves
• Title not available (Why is that?)
• Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
• On some metric and combinatorial geometric problems
• On some problems of elementary and combinatorial geometry
• A combinatorial problem on polynomials and rational functions
• Distinct distances on algebraic curves in the plane
• Incidences in three dimensions and distinct distances in the plane
• A note on distinct distances in rectangular lattices
• A note on the number of distinct distances
• Distinct distances on two lines
• Distinct distances from three points
• Distinct distances on curves via rigidity

Cited In (8)

• A note on distinct distances in rectangular lattices
• Bisector energy and few distinct distances
• Distinct Distances on Algebraic Curves in the Plane
• Distinct Distances Between a Circle and a Generic Set
• Distinct distances between a collinear set and an arbitrary set of points
• Distinct distances between points and lines
• Distinct angle problems and variants
• Sets with few distinct distances do not have heavy lines

This page was built for publication: Few distinct distances implies no heavy lines or circles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1701352)