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. S. Besicovitch, A general form of the covering principle and relative differentiation of additive functions (I), (II), Proc. Cambridge Philos. Soc. 41 (1945), 103-110; 42 (1946), 1-10.
- 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 F. Harary, M. S. Jacobson, M. J. Lipman, and F. R. McMorris, On abstract sphere-of-influence graphs, J. Comput. Geom. Theory Appl. (submitted). G. A. Kabatjanskiǐ and V. I. Levenštein, Bounds for packings on a sphere and in a space, Problemy Peredaci Informatsii 14 (1978), 3-25; English transl., Problems Inform. Transmission 14 (1978), 1-17.
- 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 J. M. Sullivan, Sphere packings give bound for the Besicovitch covering theorem, J. Geom. Anal. (to appear).
- 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 I. M. Yaglom and V. G. Boltyanskiǐ, Convex figures, Holt, Rinehart, and Winston, New York, 1961.
- 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 André E. Kézdy and Grzegorz Kubicki, ${K_{12}}$ is not a closed sphere-of-influence graph (to appear).
- 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
Additional Information
- © Copyright 1994 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 121 (1994), 1063-1073
- MSC: Primary 28A75; Secondary 05B40, 52C17
- DOI: https://doi.org/10.1090/S0002-9939-1994-1249875-4
- MathSciNet review: 1249875