Lund, Ben and Sheffer, Adam and de Zeeuw, Frank
(2016)
*Bisector Energy and Few Distinct Distances.*
Discrete and Computational Geometry, 56
(2).
pp. 337-356.
ISSN 0179-5376.
doi:10.1007/s00454-016-9783-5.
https://resolver.caltech.edu/CaltechAUTHORS:20160909-102526744

PDF
- Submitted Version
See Usage Policy. 423kB |

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160909-102526744

## Abstract

We define the bisector energyE(P) of a set P in R^2 to be the number of quadruples (a,b,c,d)∈P^4 such that a, b determine the same perpendicular bisector as c, d. Equivalently, E(P) is the number of isosceles trapezoids determined by P. We prove that for any ε>0, if an n-point set P has no M(n) points on a line or circle, then we have E(P)=O(M(n)^(2/5)n^(12/5+ε) +M(n)n^2). We derive the lower bound E(P)=Ω(M(n)n^2), matching our upper bound when M(n) is large. We use our upper bound on E(P) to obtain two rather different results: (i) If P determines O(n/√log n) distinct distances, then for any 0<α≤1/4, there exists a line or circle that contains at least n^α points of P, or there exist Ω(n^(8/5−12α/5−ε)) distinct lines that contain Ω(/√log n) points of P. This result provides new information towards a conjecture of Erdős (Discrete Math 60:147–153, 1986) regarding the structure of point sets with few distinct distances. (ii) If no line or circle contains M(n) points of P, the number of distinct perpendicular bisectors determined by P is Ω(min{M(n)^(−2/5)n^(8/5−ε), M(n)^(-1) n^2}).

Item Type: | Article | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

Related URLs: |
| ||||||||||||

ORCID: |
| ||||||||||||

Additional Information: | © 2016 Springer Science+Business Media New York. First Online: 08 June 2016. Part of this research was performed while the authors were visiting the Institute for Pure and Applied Mathematics (IPAM) in Los Angeles, which is supported by the National Science Foundation. Work on this paper by Frank de Zeeuw was partially supported by Swiss National Science Foundation Grants 200020-144531 and 200021-137574. Work on this paper by Ben Lund was supported by NSF grant CCF-1350572. | ||||||||||||

Funders: |
| ||||||||||||

Subject Keywords: | Discrete geometry; Incidence geometry; Polynomial method; Distinct distances; Perpendicular bisectors | ||||||||||||

Issue or Number: | 2 | ||||||||||||

DOI: | 10.1007/s00454-016-9783-5 | ||||||||||||

Record Number: | CaltechAUTHORS:20160909-102526744 | ||||||||||||

Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20160909-102526744 | ||||||||||||

Official Citation: | Lund, B., Sheffer, A. & de Zeeuw, F. Discrete Comput Geom (2016) 56: 337. doi:10.1007/s00454-016-9783-5 | ||||||||||||

Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||

ID Code: | 70237 | ||||||||||||

Collection: | CaltechAUTHORS | ||||||||||||

Deposited By: | Tony Diaz | ||||||||||||

Deposited On: | 09 Sep 2016 17:40 | ||||||||||||

Last Modified: | 11 Nov 2021 04:26 |

Repository Staff Only: item control page