Bisector Energy and Few Distinct Distances

We define the bisector energy E(P) of a set P in R-2 to be the number of quadruples (a, b, c, d) is an element of 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 epsilon > 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+epsilon) + M(n)n(2)). We derive the lower bound E(P) = Omega(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/root log n) distinct distances, then for any 0 < alpha <= 1/4, there exists a line or circle that contains at least na points of P, or there exist Omega(n(8/5-12 alpha/5-epsilon)) distinct lines that contain Omega(root log n) points of P. This result provides new information towards a conjecture of Erdos (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 Omega(min{M(n)(-2/5)n(8/5-epsilon), M(n)(-1)n(2)}).

Published in:
Discrete & Computational Geometry, 56, 2, 337-356
New York, Springer

 Record created 2016-10-18, last modified 2018-12-03

Rate this document:

Rate this document:
(Not yet reviewed)