License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.537
URN: urn:nbn:de:0030-drops-51086
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5108/
Go to the corresponding LIPIcs Volume Portal

Lund, Ben ; Sheffer, Adam ; de Zeeuw, Frank

Bisector Energy and Few Distinct Distances

pdf-format:
25.pdf (0.6 MB)

Abstract

We introduce the bisector energy of an n-point set P in the real plane, defined as the number of quadruples (a,b,c,d) from P such that a and b determine the same perpendicular bisector as c and d. If no line or circle contains M(n) points of P, then we prove that the bisector energy is O(M(n)^{2/5}n^{12/5} + M(n)n^2). We also prove the lower bound M(n)n^2, which matches our upper bound when M(n) is large. We use our upper bound on the bisector energy to obtain two rather different results:

(i) If P determines O(n / sqrt(log n)) distinct distances, then for any 0 < a < 1/4, either there exists a line or circle that contains n^a points of P, or there exist n^{8/5 - 12a/5} distinct lines that contain sqrt(log n) points of P. This result provides new information on a conjecture of Erdös regarding the structure of point sets with few distinct distances.

(ii) If no line or circle contains M(n) points of P, then the number of distinct perpendicular bisectors determined by P is min{M(n)^{-2/5}n^{8/5}, M(n)^{-1}n^2}). This appears to be the first higher-dimensional example in a framework for studying the expansion properties of polynomials and rational functions over the real numbers, initiated by Elekes and Ronyai.

BibTeX - Entry

@InProceedings{lund_et_al:LIPIcs:2015:5108,
  author =	{Ben Lund and Adam Sheffer and Frank de Zeeuw},
  title =	{{Bisector Energy and Few Distinct Distances}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{537--552},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Lars Arge and J{\'a}nos Pach},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5108},
  URN =		{urn:nbn:de:0030-drops-51086},
  doi =		{10.4230/LIPIcs.SOCG.2015.537},
  annote =	{Keywords: Combinatorial geometry, distinct distances, incidence geometry}
}

Keywords: Combinatorial geometry, distinct distances, incidence geometry
Collection: 31st International Symposium on Computational Geometry (SoCG 2015)
Issue Date: 2015
Date of publication: 12.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI