On the best constant for the Besicovitch covering theorem

Füredi, Zoltán; Loeb, Peter A.

doi:10.1090/S0002-9939-1994-1249875-4

On the best constant for the Besicovitch covering theorem
HTML articles powered by AMS MathViewer

by Zoltán Füredi and Peter A. Loeb PDF

Proc. Amer. Math. Soc. 121 (1994), 1063-1073 Request permission

Abstract:

This note shows that in terms of known proofs of the Besicovitch Covering Theorem, the best constant for that theorem is the maximum number of points that can be packed into a closed ball of radius 2 when the distance between pairs of points is at least 1 and one of the points is at the center of the ball. Exponential upper and lower bounds are also established.

References

M. Ajtai, The solution of a problem of T. Radó, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 21 (1973), 61–63 (English, with Russian summary). MR 319053
David Avis and Joe Horton, Remarks on the sphere of influence graph, Discrete geometry and convexity (New York, 1982) Ann. New York Acad. Sci., vol. 440, New York Acad. Sci., New York, 1985, pp. 323–327. MR 809216, DOI 10.1111/j.1749-6632.1985.tb14563.x
Paul Bateman and Paul Erdös, Geometrical extrema suggested by a lemma of Besicovitch, Amer. Math. Monthly 58 (1951), 306–314. MR 41466, DOI 10.2307/2307717

A general form of the covering principle and relative differentiation of additive functions

41

42

K. Bezdek and R. Connelly, Intersection points, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 31 (1988), 115–127 (1989). MR 1003637
J. Bliedtner and P. Loeb, A reduction technique for limit theorems in analysis and probability theory, Ark. Mat. 30 (1992), no. 1, 25–43. MR 1171093, DOI 10.1007/BF02384860
Béla Bollobás, Graph theory, Graduate Texts in Mathematics, vol. 63, Springer-Verlag, New York-Berlin, 1979. An introductory course. MR 536131, DOI 10.1007/978-1-4612-9967-7
Herbert Edelsbrunner, Günter Rote, and Emo Welzl, Testing the necklace condition for shortest tours and optimal factors in the plane, Theoret. Comput. Sci. 66 (1989), no. 2, 157–180. MR 1019083, DOI 10.1016/0304-3975(89)90133-3
L. Fejes Tóth and A. Heppes, A variant of the problem of the thirteen spheres, Canadian J. Math. 19 (1967), 1092–1100. MR 216371, DOI 10.4153/CJM-1967-100-x
Z. Füredi, J. C. Lagarias, and F. Morgan, Singularities of minimal surfaces and networks and related extremal problems in Minkowski space, Discrete and computational geometry (New Brunswick, NJ, 1989/1990) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 6, Amer. Math. Soc., Providence, RI, 1991, pp. 95–109. MR 1143291, DOI 10.1090/dimacs/006/06
P. Gritzmann and J. M. Wills, Finite packing and covering, Studia Sci. Math. Hungar. 21 (1986), no. 1-2, 149–162. MR 898852

On abstract sphere-of-influence graphs

Bounds for packings on a sphere and in a space

14

D. T. Lee, Relative neighborhood graphs in the $L_1$-metric, Pattern Recognition 18 (1985), no. 5, 327–332. MR 812198, DOI 10.1016/0031-3203(85)90023-8
Peter A. Loeb, On the Besicovitch covering theorem, SUT J. Math. 25 (1989), no. 1, 51–55. MR 1049602
Peter A. Loeb, An optimization of the Besicovitch covering, Proc. Amer. Math. Soc. 118 (1993), no. 3, 715–716. MR 1132415, DOI 10.1090/S0002-9939-1993-1132415-7
V. D. Milman, Almost Euclidean quotient spaces of subspaces of a finite-dimensional normed space, Proc. Amer. Math. Soc. 94 (1985), no. 3, 445–449. MR 787891, DOI 10.1090/S0002-9939-1985-0787891-1
Anthony P. Morse, Perfect blankets, Trans. Amer. Math. Soc. 61 (1947), 418–442. MR 20618, DOI 10.1090/S0002-9947-1947-0020618-0
Gilles Pisier, The volume of convex bodies and Banach space geometry, Cambridge Tracts in Mathematics, vol. 94, Cambridge University Press, Cambridge, 1989. MR 1036275, DOI 10.1017/CBO9780511662454
E. R. Reifenberg, A problem on circles, Math. Gaz. 32 (1948), 290–292. MR 30216, DOI 10.2307/3609890
Claude E. Shannon, Probability of error for optimal codes in a Gaussian channel, Bell System Tech. J. 38 (1959), 611–656. MR 103137, DOI 10.1002/j.1538-7305.1959.tb03905.x

Sphere packings give bound for the Besicovitch covering theorem

H. P. F. Swinnerton-Dyer, Extremal lattices of convex bodies, Proc. Cambridge Philos. Soc. 49 (1953), 161–162. MR 51880, DOI 10.1017/s0305004100028188
Godfried T. Toussaint, Computational geometric problems in pattern recognition, Pattern recognition theory and applications (Oxford, 1981) NATO Adv. Study Inst. Ser. C: Math. Phys. Sci., vol. 81, Reidel, Dordrecht, 1982, pp. 73–91. MR 775510

Convex figures

L. Guibas, J. Pach, and M. Sharir, Sphere-of-influence graphs in higher dimensions, Intuitive geometry (Szeged, 1991) Colloq. Math. Soc. János Bolyai, vol. 63, North-Holland, Amsterdam, 1994, pp. 131–137. MR 1383618
Steven G. Krantz and T. D. Parsons, Antisocial subcovers of self-centered coverings, Amer. Math. Monthly 93 (1986), no. 1, 45–48. MR 824589, DOI 10.2307/2322545

is not a closed sphere-of-influence graph

A. Malnič and B. Mohar, Two results on antisocial families of balls, Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (Prachatice, 1990) Ann. Discrete Math., vol. 51, North-Holland, Amsterdam, 1992, pp. 205–207. MR 1206267, DOI 10.1016/S0167-5060(08)70629-0
T. S. Michael and T. Quint, Sphere of influence graphs: edge density and clique size, Math. Comput. Modelling 20 (1994), no. 7, 19–24. MR 1299482, DOI 10.1016/0895-7177(94)90067-1