Few distinct distances implies no heavy lines or circles
We study the structure of planar point sets that determine a small number of distinct distances. Specifically, we show that if a set PP of n points determines o(n) distinct distances, then no line contains Ω(n[superscript 7/8]) points of PP and no circle contains Ω(n[superscript 5/6]) points of...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2017
|
| Online Access: | http://hdl.handle.net/1721.1/106218 https://orcid.org/0000-0001-5129-8300 |
| Summary: | We study the structure of planar point sets that determine a small number of distinct distances. Specifically, we show that if a set PP of n points determines o(n) distinct distances, then no line contains Ω(n[superscript 7/8]) points of PP and no circle contains Ω(n[superscript 5/6]) points of PP .
We rely on the partial variant of the Elekes-Sharir framework that was introduced by Sharir, Sheffer, and Solymosi in [19] for bipartite distinct distance problems. To prove our bound for the case of lines we combine this framework with a theorem from additive combinatorics, and for our bound 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 [20].
A significant difference between our approach and that of [19] (and of other related results) 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. |
|---|