Hostname: page-component-76fb5796d-dfsvx Total loading time: 0 Render date: 2024-04-26T18:05:35.348Z Has data issue: false hasContentIssue false
  • English
  • Français

Distinct Distances from Three Points

Part of: Graph theory Discrete geometry

Published online by Cambridge University Press:  30 September 2015

MICHA SHARIR  and
JÓZSEF SOLYMOSI
MICHA SHARIR
Affiliation:
School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: michas@tau.ac.il)
JÓZSEF SOLYMOSI
Affiliation:
Department of Mathematics, University of British Columbia, Vancouver BC, V6T 1Z4, Canada (e-mail: solymosi@math.ubc.ca)
Get access Rights & Permissions [Opens in a new window]

Abstract

Let p1, p2, p3 be three noncollinear points in the plane, and let P be a set of n other points in the plane. We show that the number of distinct distances between p1, p2, p3 and the points of P is Ω(n6/11), improving the lower bound Ω(n0.502) of Elekes and Szabó [4] (and considerably simplifying the analysis).

MSC classification

Primary: 52C10: Erdős problems and related topics of discrete geometry
Secondary: 52C45: Combinatorial complexity of geometric structures 05C35: Extremal problems
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 4 , July 2016 , pp. 623 - 632
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Elekes, G. (2002) Sums versus products in number theory, algebra and Erdős geometry: A survey. In Paul Erdős and his Mathematics II, Vol. 11 of Bolyai Mathematical Society Studies, Budapest, pp. 241–290.Google Scholar
[2] Elekes, G. and Rónyai, L. (2000) A combinatorial problem on polynomials and rational functions, J. Combin. Theory Ser. A 89 1–20.Google Scholar
[3] Elekes, G., Simonovits, M. and Szabó, E. (2009) A combinatorial distinction between unit circles and straight lines: How many coincidences can they have? Combin. Probab. Comput. 18 691–705.Google Scholar
[4] Elekes, G. and Szabó, E. (2012) How to find groups? (and how to use them in Erdős geometry?) Combinatorica 32 537–571.Google Scholar
[5] Erdős, P., Lovász, L. and Vesztergombi, K. (1989) On the graph of large distance. Discrete Comput. Geom. 4 541–549.Google Scholar
[6] Pach, J. and Sharir, M. (1998) On the number of incidences between points and curves. Combin. Probab. Comput. 7 121–127.Google Scholar
[7] Pach, J. and de Zeeuw, F. (2014) Distinct distances on algebraic curves in the plane. In Proc. 30th Symposium on Computational Geometry, pp. 549–557. Also in arXiv:1308.0177.Google Scholar
[8] Sharir, M., Sheffer, A. and Solymosi, J. (2013) Distinct distances on two lines. J. Combin. Theory Ser. A 20 1732–1736.Google Scholar
[9] Székely, L. (1997) Crossing numbers and hard Erdős problems in discrete geometry. Combin. Probab. Comput. 6 353–358.Google Scholar