Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-29T15:24:43.914Z 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: [email protected])
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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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].

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 4 , July 2011 , pp. 503 - 512
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]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