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

Non-Degenerate Spheres in Three Dimensions

Published online by Cambridge University Press:  28 January 2011

ROEL APFELBAUM  and
MICHA SHARIR
ROEL APFELBAUM
Affiliation:
School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: roel6@hotmail.com)
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@post.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.

Let P be a set of n points in ℝ3, and let k ≤ n be an integer. A sphere σ is k-rich with respect to P if |σ ∩ P| ≥ k, and is η-non-degenerate, for a fixed fraction 0 < η < 1, if no circle γ ⊂ σ contains more than η|σ ∩ P| points of P.

We improve the previous bound given in [1] on the number of k-rich η-non-degenerate spheres in 3-space with respect to any set of n points in ℝ3, from O(n4/k5 + n3/k3), which holds for all 0 < η < 1/2, to O*(n4/k11/2 + n2/k2), which holds for all 0 < η < 1 (in both bounds, the constants of proportionality depend on η). The new bound implies the improved upper bound O*(n58/27) ≈ O(n2.1482) on the number of mutually similar triangles spanned by n points in ℝ3; the previous bound was O(n13/6) ≈ O(n2.1667) [1].

Information

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

References

[1]Agarwal, P. K., Apfelbaum, R., Purdy, G. and Sharir, M. (2007) Similar simplices in a d-dimensional point set. In Proc. 23rd Annu. ACM Sympos. Comput. Geom., pp. 232–238.CrossRefGoogle Scholar
[2]Agarwal, P. K., Nevo, E., Pach, J., Pinchasi, R., Sharir, M. and Smorodinsky, S. (2004) Lenses in arrangements of pseudocircles and their applications. J. Assoc. Comput. Mech. 51 139–186.CrossRefGoogle Scholar
[3]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
[4]Aronov, B., Pach, J., Sharir, M. and Tardos, G. (2004) Distinct distances in three and higher dimensions. Combin. Probab. Comput. 13 283–293.CrossRefGoogle Scholar
[5]Aronov, B. and Sharir, M. (2002) Cutting circles into pseudo-segments and improved bounds for incidences. Discrete Comput. Geom. 28 475–490.CrossRefGoogle Scholar
[6]Chazelle, B. (2005) Cuttings. In Handbook of Data Structures and Applications (Mehta, D. and Sahni, S., eds), Chap. 25, Chapman and Hall/CRC Press.Google Scholar
[7]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
[8]Edelsbrunner, H. (1987) Algorithms in Combinatorial Geometry, Springer.CrossRefGoogle Scholar
[9]Elekes, G. and Tóth, C. D. (2005) Incidences of not too degenerate hyperplanes. In Proc. 21st Annu. ACM Sympos. Comput. Geom., pp. 16–21.CrossRefGoogle Scholar
[10]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, pp. 119–126.CrossRefGoogle Scholar
[11]Marcus, A. and Tardos, G. (2006) Intersection reverse sequences and geometric applications. J. Combin. Theory Ser. A 113 675–691.CrossRefGoogle Scholar
[12]Solymosi, J. and Vu, V. (2006) Near optimal bounds for the Erdős distinct distances problem in high dimensions. Combinatorica 28 113–125.CrossRefGoogle Scholar