Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T13:53:12.514Z Has data issue: false hasContentIssue false
  • English
  • Français

Incidences in Three Dimensions and Distinct Distances in the Plane†

Published online by Cambridge University Press:  04 April 2011

GYÖRGY ELEKES  and
MICHA SHARIR
GYÖRGY ELEKES
Affiliation:
Department of Computer Science, Eötvös University, Budapest, Hungary
MICHA SHARIR
Affiliation:
School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, NY 10012, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We first describe a reduction from the problem of lower-bounding the number of distinct distances determined by a set S of s points in the plane to an incidence problem between points and a certain class of helices (or parabolas) in three dimensions. We offer conjectures involving the new set-up, but are still unable to fully resolve them.

Instead, we adapt the recent new algebraic analysis technique of Guth and Katz [9], as further developed by Elekes, Kaplan and Sharir [6], to obtain sharp bounds on the number of incidences between these helices or parabolas and points in ℝ3. Applying these bounds, we obtain, among several other results, the upper bound O(s3) on the number of rotations (rigid motions) which map (at least) three points of S to three other points of S. In fact, we show that the number of such rotations which map at least k ≥ 3 points of S to k other points of S is close to O(s3/k12/7).

One of our unresolved conjectures is that this number is O(s3/k2), for k ≥ 2. If true, it would imply the lower bound Ω(s/logs) on the number of distinct distances in the plane.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 4 , July 2011 , pp. 571 - 608
Copyright
Copyright © Cambridge University Press 2011

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]Alon, N. and Spencer, J. (1992) The Probabilistic Method, Wiley-Interscience.Google Scholar
[2]Aronov, B., Koltun, V. and Sharir, M. (2005) Incidences between points and circles in three and higher dimensions. Discrete Comput. Geom. 33 185–206.CrossRefGoogle Scholar
[3]Brass, P., Moser, W. and Pach, J. (2005) Research Problems in Discrete Geometry, Springer.Google Scholar
[4]Chung, F. R. K. (1984) The number of different distances determined by n points in the plane. J. Combin. Theory Ser. A 36 342–354.CrossRefGoogle Scholar
[5]Chung, F. R. K., Szemerédi, E. and Trotter, W. T. (1992) The number of different distances determined by a set of points in the Euclidean plane. Discrete Comput. Geom. 7 1–11.Google Scholar
[6]Elekes, G., Kaplan, H. and Sharir, M. (2011) On lines, joints, and incidences in three dimensions. J. Combin. Theory Ser. A 118 962–977. Also in arXiv:0905.1583.Google Scholar
[7]Erdős, P. (1946) On sets of distances of n points. Amer. Math. Monthly 53 248–250.Google Scholar
[8]Gray, A. (1997) Modern Differential Geometry of Curves and Surfaces with Mathematica, 2nd edition, CRC Press.Google Scholar
[9]Guth, L. and Katz, N. H. (2010) Algebraic methods in discrete analogs of the Kakeya problem. Adv. Math. 225 2828–2839. Also in arXiv:0812.1043v1.Google Scholar
[10]Guth, L. and Katz, N. H. On the Erdős distinct distances problem in the plane. arXiv:1011.4105.Google Scholar
[11]Haussler, D. and Welzl, E. (1987) Epsilon nets and simplex range queries. Discrete Comput. Geom. 2 127–151.CrossRefGoogle Scholar
[12]Kaplan, H., Sharir, M. and Shustin, E. (2010) On lines and joints. Discrete Comput. Geom. 44 838–843. Also in arXiv:0906.0558.Google Scholar
[13]Katz, N. H. and Tardos, G. (2004) A new entropy inequality for the Erdős distance problem. In Towards a Theory of Geometric Graphs (Pach, J., ed.), Vol. 342 of Contemporary Mathematics, AMS Press, pp. 119–126.CrossRefGoogle Scholar
[14]Moser, L. (1952) On the different distances determined by n points. Amer. Math. Monthly 59 85–91.CrossRefGoogle Scholar
[15]Pressley, A. (2001) Elementary Differential Geometry, Springer Undergraduate Mathematics Series, Springer.CrossRefGoogle Scholar
[16]Quilodrán, R. (2010) The joints problem in ℝn. SIAM J. Discrete Math. 23 2211–2213. Also in arXiv:0906.0555.CrossRefGoogle Scholar
[17]Shafarevich, I. R. (1977) Basic Algebraic Geometry, Springer.Google Scholar
[18]Sharir, M. (2009) On distinct distances and incidences: Elekes's transformation and the new algebraic developments. Annales Univ. Sci. Budapest. 52 75–102.Google Scholar
[19]Sharir, M. and Welzl, E. (2004) Point–line incidences in space. Combin. Probab. Comput. 13 203–220.CrossRefGoogle Scholar
[20]Solymosi, J. and Tóth, C. D. (2008) On a question of Bourgain about geometric incidences. Combin. Probab. Comput. 17 619–625.CrossRefGoogle Scholar
[21]Spencer, J., Szemerédi, E. and Trotter, W. T. (1984) Unit distances in the Euclidean plane. In Graph Theory and Combinatorics (Bollobás, B., ed.), Academic Press, 293–303.Google Scholar
[22]Székely, L. (1997) Crossing numbers and hard Erdős problems in discrete geometry. Combin. Probab. Comput. 6 353–358.Google Scholar
[23]Szemerédi, E. and Trotter, W. T. (1983) Extremal problems in discrete geometry. Combinatorica 3 381–392.CrossRefGoogle Scholar
[24]Tardos, G. (2003) On distinct sums and distinct distances. Adv. Math. 180 275–289.CrossRefGoogle Scholar