[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Bisector Energy and Few Distinct Distances

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

Abstract

We define the bisector energy \(\mathcal E(\mathcal P)\) of a set \(\mathcal P\) in \(\mathbb R^2\) to be the number of quadruples \((a,b,c,d)\in \mathcal P^4\) such that a, b determine the same perpendicular bisector as c, d. Equivalently, \(\mathcal E(\mathcal P)\) is the number of isosceles trapezoids determined by \(\mathcal P\). We prove that for any \(\varepsilon >0\), if an n-point set \(\mathcal P\) has no M(n) points on a line or circle, then we have

$$\begin{aligned} \mathcal E(\mathcal P) = O\big (M(n)^{\frac{2}{5}}n^{\frac{12}{5}+\varepsilon } + M(n)n^2\big ). \end{aligned}$$

We derive the lower bound \(\mathcal E(\mathcal P)=\Omega (M(n)n^2)\), matching our upper bound when M(n) is large. We use our upper bound on \(\mathcal E(\mathcal P)\) to obtain two rather different results:

  1. (i)

    If \(\mathcal P\) determines \(O(n/\sqrt{\log n})\) distinct distances, then for any \(0<\alpha \le 1/4\), there exists a line or circle that contains at least \(n^\alpha \) points of \(\mathcal P\), or there exist \(\Omega (n^{8/5-12\alpha /5-\varepsilon })\) distinct lines that contain \(\Omega (\sqrt{\log n})\) points of \(\mathcal 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.

  2. (ii)

    If no line or circle contains M(n) points of \(\mathcal P\), the number of distinct perpendicular bisectors determined by \(\mathcal P\) is \(\Omega \left( \min \left\{ M(n)^{-2/5}n^{8/5-\varepsilon }, M(n)^{-1} n^2\right\} \right) \).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Notes

  1. Throughout this paper, when we state a bound involving an \(\varepsilon \), we mean that this bound holds for every \(\varepsilon >0\), with the multiplicative constant of the O()-notation depending on \(\varepsilon \).

  2. We define the dimension of a real algebraic variety as in [3, Sect. 2.8].

  3. This lemma only applies to complex varieties. However, we can take the complexification of the real variety and apply the lemma to it (for the definition of a complexification, see for example [27, Sect. 10]). The number of irreducible components of the complexification cannot be smaller than number of irreducible components of the real variety (see for instance [27, Lem. 7]).

References

  1. Beck, J.: On the lattice property of the plane and some problems of Dirac, Motzkin, and Erdős in combinatorial geometry. Combinatorica 3, 281–297 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bollobás, B.: Graph Theory: An Introductory Course. Springer, New York (1979)

    Book  MATH  Google Scholar 

  3. Bochnak, J., Coste, M., Roy, M.F.: Real Algebraic Geometry. Springer, Berlin (2013)

    MATH  Google Scholar 

  4. Elekes, G., Rónyai, L.: A combinatorial problem on polynomials and rational functions. J. Comb. Theory, Ser. A 89, 1–20 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  5. Elekes, G., Szabó, E.: How to find groups? (And how to use them in Erdős geometry?). Combinatorica 32, 537–571 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  6. Elekes, G., Szabó, E.: On triple lines and cubic curves: the Orchard Problem revisited. http://arxiv.org/abs/1302.5777

  7. Erdős, P.: On sets of distances of \(n\) points. Am. Math. Mon. 53, 248–250 (1946)

    Article  MathSciNet  MATH  Google Scholar 

  8. Erdős, P.: On some problems of elementary and combinatorial geometry. Ann. Mat. Pura Appl. 103, 99–108 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  9. Erdős, P.: On some metric and combinatorial geometric problems. Discrete Math. 60, 147–153 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  10. Erdős, P., Purdy, G.: Some extremal problems in geometry IV. In: Proceedings of 7th Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp. 307–322 (1976)

  11. Fox, J., Pach, J., Sheffer, A., Suk, A., Zahl, J.: A semi-algebraic version of Zarankiewicz’s problem. J. Eur. Math. Soc. (to appear)

  12. Green, B., Tao, T.: On sets defining few ordinary lines. Discrete Comput. Geom. 50, 409–468 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  13. Guth, L., Katz, N.H.: On the Erdős distinct distances problem in the plane. Ann. Math. 181, 155–190 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  14. Hanson, B., Lund, B., Roche-Newton, O.: On distinct perpendicular bisectors and pinned distances in finite fields. Finite Fields Appl. 37, 240–264 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  15. Katz, N.H., Tardos, G.: A new entropy inequality for the Erdős distance problem, Towards a Theory of Geometric Graphs (J. Pach, ed.). Contemp. Math. 342, 119–126 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  16. Pach, J., Tardos, G.: Isosceles triangles determined by a planar point set. Graphs Comb. 18, 769–779 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  17. Pach, J., Zeeuw, F. de.: Distinct distances on algebraic curves in the plane. Comb. Probab. Comput. (to appear)

  18. Raz, O.E., Roche-Newton, O., Sharir, M.: Sets with few distinct distances do not have heavy lines. Discrete Math. 338, 1484–1492 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  19. Raz, O.E., Sharir, M., Solymosi, J.: Polynomials vanishing on grids: the Elekes-Rónyai problem revisited. Am. J. Math. (to appear)

  20. Raz, O.E., Sharir, M., de Zeeuw, F.: Polynomials vanishing on Cartesian products: the Elekes-Szabó theorem revisited. Duke Math. J. (to appear)

  21. Sheffer, A.: Few distinct distances implies many points on a line. Blog post (2014)

  22. Sheffer, A., Zahl, J., de Zeeuw, F.: Few distinct distances implies no heavy lines or circles. Combinatorica. (to appear)

  23. Solymosi, J., Stojaković, M.: Many collinear \(k\)-tuples with no \(k+ 1\) collinear points. Discrete Comput. Geom. 50, 811–820 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  24. Solymosi, J., Tao, T.: An incidence theorem in higher dimensions. Discrete Comput. Geom. 48, 255–280 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  25. Szemerédi, E., Trotter, W.: Extremal problems in discrete geometry. Combinatorica 3, 381–392 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  26. Tardos, G.: On distinct sums and distinct distances. Adv. Math. 180, 275–289 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  27. Whitney, H.: Elementary structure of real algebraic varieties. Ann. Math. 66, 545–556 (1957)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

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.

Author information

Authors and Affiliations

  1. Rutgers University, New Brunswick, NJ, USA

    Ben Lund

  2. California Institute of Technology, Pasadena, CA, USA

    Adam Sheffer

  3. EPFL, Lausanne, Switzerland

    Frank de Zeeuw

Authors
  1. Ben Lund
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Adam Sheffer
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Frank de Zeeuw
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Adam Sheffer.

Additional information

Editor in Charge: János Pach

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lund, B., Sheffer, A. & de Zeeuw, F. Bisector Energy and Few Distinct Distances. Discrete Comput Geom 56, 337–356 (2016). https://doi.org/10.1007/s00454-016-9783-5

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-016-9783-5

Keywords

Search

Navigation