×

Non-degenerate spheres in three dimensions. (English) Zbl 1222.52023

Summary: Let \(P\) be a set of \(n\) points in \(\mathbb R^3\), and let \(k\leq n\) be an integer. A sphere \(\sigma\) is \(k\)-rich with respect to \(P\) if \(|\sigma \cap P|\geq k\), and is \(\eta\)-non-degenerate, for a fixed fraction \(0<\eta<1\), if no circle \(\gamma\subset\sigma\) contains more than \(\eta|\sigma \cap P|\) points of \(P\). We improve the previous bound given in [P. K. Agarwal, R. Apfelbaum, G. Purdy, and M. Sharir, Similar simplices in a \(d\)-dimensional point set. Proceedings of the 23rd annual symposium on computational geometry 2007, Gyeongiu, South Korea, June 6–8, 2007. New York, NY: Association for Computing Machinery. 232–238 (2007; Zbl 1218.52021)] on the number of \(k\)-rich \(\eta\)-non-degenerate spheres in 3-space with respect to any set of \(n\) points in \(\mathbb R^3\), from \(O(n^4/k^5+n^3/k^3)\), which holds for all \(0<\eta<1/2\), to \(O^*(n^4/k^{11/2} +n^2/k^2)\), which holds for all \(0<\eta<1\) (in both bounds, the constants of proportionality depend on \(\eta\)). The new bound implies the improved upper bound \(O^*(n^{58/27})\approx O(n^{2.1482})\) on the number of mutually similar triangles spanned by \(n\) points in \(\mathbb R^3\); the previous bound was \(O(n^{13/6})\approx O(n^{2.1667})\) [loc. cit.].

MSC:

52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)

Citations:

Zbl 1218.52021
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Edelsbrunner, Algorithms in Combinatorial Geometry (1987) · doi:10.1007/978-3-642-61568-9
[2] DOI: 10.1007/BF02187783 · Zbl 0704.51003 · doi:10.1007/BF02187783
[3] Chazelle, Handbook of Data Structures and Applications (2005)
[4] Aronov, Discrete Comput. Geom. 28 pp 475– (2002) · Zbl 1050.68143 · doi:10.1007/s00454-001-0084-1
[5] Katz, Towards a Theory of Geometric Graphs pp 119– (2004) · doi:10.1090/conm/342/06136
[6] DOI: 10.1007/s00454-004-1111-9 · Zbl 1080.68102 · doi:10.1007/s00454-004-1111-9
[7] Agarwal, J. Assoc. Comput. Mech. 51 pp 139– (2004) · Zbl 1317.52031 · doi:10.1145/972639.972641
[8] DOI: 10.1007/s00493-008-2099-1 · Zbl 1174.52009 · doi:10.1007/s00493-008-2099-1
[9] DOI: 10.1016/j.jcta.2005.07.002 · Zbl 1140.05022 · doi:10.1016/j.jcta.2005.07.002
[10] DOI: 10.1017/S0963548304006091 · Zbl 1052.52010 · doi:10.1017/S0963548304006091
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.