Hostname: page-component-745bb68f8f-s22k5 Total loading time: 0 Render date: 2025-02-12T00:29:17.121Z Has data issue: false hasContentIssue false
  • English
  • Français

Unit Distances in Three Dimensions

Published online by Cambridge University Press:  25 April 2012

HAIM KAPLAN ,
JIŘÍ MATOUŠEK ,
ZUZANA SAFERNOVÁ  and
MICHA SHARIR
HAIM KAPLAN
Affiliation:
School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: haimk@tau.ac.il)
JIŘÍ MATOUŠEK
Affiliation:
Department of Applied Mathematics and Institute of Theoretical Computer Science (ITI), Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic (e-mail: matousek@kam.mff.cuni.cz) and Institute of Theoretical Computer Science, ETH Zurich, 8092 Zurich, Switzerland
ZUZANA SAFERNOVÁ
Affiliation:
Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic (e-mail: zuzka@kam.mff.cuni.cz)
MICHA SHARIR
Affiliation:
School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA (e-mail: michas@tau.ac.il)
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.

We show that the number of unit distances determined by n points in ℝ3 is O(n3/2), slightly improving the bound of Clarkson, Edelsbrunner, Guibas, Sharir and Welzl [5], established in 1990. The new proof uses the recently introduced polynomial partitioning technique of Guth and Katz [12]. While this paper was still in a draft stage, a similar proof of our main result was posted to the arXiv by Joshua Zahl [28].

Keywords

Primary 52C10
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 4 , July 2012 , pp. 597 - 610
Copyright
Copyright © Cambridge University Press 2012

References

[1]Akama, Y., Irie, K., Kawamura, A. and Uwano, Y. (2010) VC dimensions of principal component analysis. Discrete Comput. Geom. 44 589–598.CrossRefGoogle Scholar
[2]Barone, S. and Basu, S. (2012) Refined bounds on the number of connected components of sign conditions on a variety. Discrete Comput. Geom. 47 (3)577–597.CrossRefGoogle Scholar
[3]Basu, S., Pollack, R. and Roy, M.-F. (1996) On the number of cells defined by a family of polynomials on a variety. Mathematika 43 120–126.CrossRefGoogle Scholar
[4]Basu, S., Pollack, R. and Roy, M.-F. (2003) Algorithms in Real Algebraic Geometry, Vol. 10 of Algorithms and Computation in Mathematics, Springer.CrossRefGoogle Scholar
[5]Clarkson, K., Edelsbrunner, H., Guibas, L., Sharir, M. and Welzl, E. (1990) Combinatorial complexity bounds for arrangements of curves and spheres. Discrete Comput. Geom. 5 99–160.CrossRefGoogle Scholar
[6]Cox, D., Little, J. and O'Shea, D. (2005) Using Algebraic Geometry, second edition, Springer.Google Scholar
[7]Cox, D., Little, J. and O'Shea, D. (2007) Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, third edition, Springer.CrossRefGoogle Scholar
[8]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.CrossRefGoogle Scholar
[9]Erdős, P. (1946) On a set of distances of n points. Amer. Math. Monthly 53 248–250.CrossRefGoogle Scholar
[10]Erdős, P. (1960) On sets of distances on n points in Euclidean space. Magyar Tud. Akad. Mat. Kutató Int. Kozl. 5 165–169.Google Scholar
[11]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.CrossRefGoogle Scholar
[12]Guth, L. and Katz, N. H. (2010) On the Erdős distinct distances problem in the plane. arXiv:1011.4105.Google Scholar
[13]Harnack, C. G. A. (1876) Über die Vielfaltigkeit der ebenen algebraischen Kurven. Math. Ann. 10 189–199.CrossRefGoogle Scholar
[14]Kaplan, H., Matoušek, J. and Sharir, M. (2011) Simple proofs of classical theorems in discrete geometry via the Guth–Katz polynomial partitioning technique. Discrete Comput. Geom., submitted. Also in arXiv:1102.5391.Google Scholar
[15]Lenz, H. (1955) Zur Zerlegung von Punktmengen in solche kleineren Durchmessers. Arch. Math. 6 413–416.CrossRefGoogle Scholar
[16]Matoušek, J. (2003) Using the Borsuk–Ulam Theorem, Springer.Google Scholar
[17]Milnor, J. (1964) On the Betti numbers of real varieties. Proc. Amer. Math. Soc. 15 275–280.CrossRefGoogle Scholar
[18]Oleinik, O. A. and Petrovskii, I. B. (1949) On the topology of real algebraic surfaces. Izv. Akad. Nauk SSSR 13 389–402.Google Scholar
[19]Pach, J. and Agarwal, P. K. (1995) Combinatorial Geometry, Wiley-Interscience.CrossRefGoogle Scholar
[20]Pach, J. and Sharir, M. (2004) Geometric incidences. In Towards a Theory of Geometric Graphs (Pach, J., ed.), Vol. 342 of Contemporary Mathematics, AMS, pp. 185–223.CrossRefGoogle Scholar
[21]Solymosi, J. and Tao, T. (2012) An incidence theorem in higher dimensions. arXiv:1103.2926v4CrossRefGoogle Scholar
[22]Spencer, J., Szemerédi, E. and Trotter, W. T. (1984) Unit distances in the Euclidean plane. In Graph Theory and Combinatorics: Proc. Cambridge Conf. on Combinatorics (Bollobás, B., ed.), Academic Press, pp. 293–308.Google Scholar
[23]Stone, A. H. and Tukey, J. W. (1942) Generalized sandwich theorems. Duke Math. J. 9 356–359.CrossRefGoogle Scholar
[24]Székely, L. (1997) Crossing numbers and hard Erdős problems in discrete geometry. Combinat. Probab. Comput. 6 353–358.CrossRefGoogle Scholar
[25]Thom, R. (1965) Sur l'homologie des variétés algébriques réelles. In Differential and Combinatorial Topology (Cairns, S. S., ed.), Princeton University Press, pp. 255–265.CrossRefGoogle Scholar
[26]Valtr, P. (2006) Strictly convex norms allowing many unit distances and related touching questions, manuscript.Google Scholar
[27]Warren, H. E. (1968) Lower bound for approximation by nonlinear manifolds. Trans. Amer. Math. Soc. 133 167–178.CrossRefGoogle Scholar
[28]Zahl, J. (2011) An improved bound on the number of point-surface incidences in three dimensions. arXiv:1104.4987. First posted (v1) 26 April 2011; revised and corrected 22 September 2011.Google Scholar