CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:20160909-102526744

[img] PDF - Submitted Version
See Usage Policy.

413Kb

Use this Persistent URL to link to this item: http://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:
URLURL TypeDescription
http://dx.doi.org/10.1007/s00454-016-9783-5DOIArticle
http://link.springer.com/article/10.1007%2Fs00454-016-9783-5PublisherArticle
https://arxiv.org/abs/1411.6868arXivDiscussion Paper
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:
Funding AgencyGrant Number
Swiss National Science Foundation (SNSF)200020-144531
Swiss National Science Foundation (SNSF)200021-137574
NSFCCF-1350572
Subject Keywords:Discrete geometry; Incidence geometry; Polynomial method; Distinct distances; Perpendicular bisectors
Record Number:CaltechAUTHORS:20160909-102526744
Persistent URL:http://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:09 Sep 2016 17:40

Repository Staff Only: item control page