Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-07T06:06:25.927Z Has data issue: false hasContentIssue false
  • English
  • Français

Distinct Distances from Three Points

Part of: Discrete geometry Graph theory

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)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let p 1, p 2, p 3 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 p 1, p 2, p 3 and the points of P is Ω(n 6/11), improving the lower bound Ω(n 0.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

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 4 , July 2016 , pp. 623 - 632
Copyright
Copyright © Cambridge University Press 2015 

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