A Caltech Library Service

Bisector Energy and Few Distinct Distances

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.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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:
URLURL TypeDescription Paper
Sheffer, Adam0000-0003-3418-5122
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.
Funding AgencyGrant Number
Swiss National Science Foundation (SNSF)200020-144531
Swiss National Science Foundation (SNSF)200021-137574
Subject Keywords:Discrete geometry; Incidence geometry; Polynomial method; Distinct distances; Perpendicular bisectors
Issue or Number:2
Record Number:CaltechAUTHORS:20160909-102526744
Persistent URL:
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
Deposited By: Tony Diaz
Deposited On:09 Sep 2016 17:40
Last Modified:11 Nov 2021 04:26

Repository Staff Only: item control page