Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



On the best constant for the Besicovitch covering theorem

Authors: Zoltán Füredi and Peter A. Loeb
Journal: Proc. Amer. Math. Soc. 121 (1994), 1063-1073
MSC: Primary 28A75; Secondary 05B40, 52C17
MathSciNet review: 1249875
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] M. Ajtai, The solution of a problem of T. Rodó, Bull. Acad. Polon. Sci. Ser. Math. Astr. Phys. 21 (1972), 61-63. MR 0319053 (47:7599)
  • [2] D. Avis and J. Horton, Remarks on the sphere of influence graph, Proc. Conf. on Discrete Geometry and Convexity (J. E. Goodman et al., eds.), New York, 1982; Ann. New York Acad. Sci., vol. 440, New York Acad. Sci., New York, 1985, pp. 323-327. MR 809216 (87i:05161)
  • [3] P. T. Bateman and P. Erdős, Geometrical extrema suggested by a lemma of Besicovitch, Amer. Math. Monthly 58 (1951), 306-314. MR 0041466 (12:851a)
  • [4] 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.
  • [5] K. Bezdek and R. Connelly, Intersection points, Ann. Univ. Sci. Budapest Sect. Math. 31 (1988), 115-127. MR 1003637 (90i:52014)
  • [6] J. Bliedtner and P. A. Loeb, A reduction technique for limit theorems in analysis and probability theory, Ark. Mat. 30 (1992), 25-43. MR 1171093 (93k:28005)
  • [7] B. Bollobás, Graph theory, Springer-Verlag, New York, 1979. MR 536131 (80j:05053)
  • [8] H. Edelsbrunner, G. Rote, and E. Welzl, Testing the necklace condition for shortest tours and optimal factors in the plane, Theoret. Comput. Sci. 66 (1989), 157-180. MR 1019083 (90i:90042)
  • [9] L. Fejes Tóth and A. Heppes, A variant of the problem of the thirteen spheres, Canad. Math. Bull. 19 (1967), 1092-1100. MR 0216371 (35:7205)
  • [10] Z. Füredi, J. Lagarias, and F. Morgan, Singularities of minimal surfaces and networks and related extremal problems in Minkowski space, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 6, Amer. Math. Soc., Providence, RI, 1991, pp. 95-109. MR 1143291 (93d:52009)
  • [11] P. Gritzmann and J. Wills, Finite packing and covering, Studia Sci. Math. Hungar. 21 (1986), 149-162. MR 898852 (88h:52022)
  • [12] F. Harary, M. S. Jacobson, M. J. Lipman, and F. R. McMorris, On abstract sphere-of-influence graphs, J. Comput. Geom. Theory Appl. (submitted).
  • [13] G. A. Kabatjanskii 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.
  • [14] D. T. Lee, Relative neighborhood graphs in the $ {L_1}$-metric, Pattern Recognition 18 (1985), 327-332. MR 812198 (87a:68149)
  • [15] P. A. Loeb, On the Besicovitch Covering Theorem, Science University of Tokyo J. Math. 25 (1989), 51-55. MR 1049602 (91c:28003)
  • [16] -, An optimization of the Besicovitch covering, Proc. Amer. Math. Soc. 118 (1993), 715-716. MR 1132415 (93i:03098)
  • [17] V. D. Milman, Almost Euclidean quotient space of subspaces of finite dimensional normed spaces, Proc. Amer. Math. Soc. 94 (1985), 445-449. MR 787891 (86g:46025)
  • [18] A. P. Morse, Perfect blankets, Trans. Amer. Math. Soc. 61 (1947), 418-442. MR 0020618 (8:571h)
  • [19] G. Pisier, The volume of convex bodies and Banach space geometry, Cambridge Tracts in Math., vol. 94, Cambridge Univ. Press, Cambridge, 1989. MR 1036275 (91d:52005)
  • [20] E. F. Reifenberg, A problem on circles, Math. Gaz. 32 (1948), 290-292. MR 0030216 (10:731a)
  • [21] C. E. Shannon, Probability of error for optimal codes in a Gaussian channel, Bell System Tech. J. 38 (1959), 611-656. MR 0103137 (21:1920)
  • [22] J. M. Sullivan, Sphere packings give bound for the Besicovitch covering theorem, J. Geom. Anal. (to appear).
  • [23] H. P. F. Swinnerton-Dyer, Extremal lattices of convex bodies, Proc. Cambridge Philos. Soc. 49 (1953), 161-162. MR 0051880 (14:540f)
  • [24] G. T. Toussaint, Computational geometric problems in pattern recognition, Pattern Recognition Theory and Application (J. Kittler, ed.), NATO Advanced Study Institute, Oxford University, 1981, pp. 73-91. MR 775510
  • [25] I. M. Yaglom and V. G. Boltyanskii, Convex figures, Holt, Rinehart, and Winston, New York, 1961.
  • [26] L. Guibas, J. Pach, and M. Sharir, Sphere-of-influence graphs in higher dimensions, Intuitive Geometry (K. Böröczky and G. Fejes Tóth, eds.), Proc. Colloq. Math. Soc. J. Bolyai, North-Holland, Amsterdam (to appear). MR 1383618 (97a:05183)
  • [27] S. G. Krantz and T. D. Parsons, Antisocial subcovers of self-centered coverings, Amer. Math. Monthly 93 (1986), 45-48. MR 824589 (87g:52027)
  • [28] André E. Kézdy and Grzegorz Kubicki, $ {K_{12}}$ is not a closed sphere-of-influence graph (to appear).
  • [29] A. Malnić and B. Mohar, Two results on an antisocial families of balls, Proc. of the Fourth Czechoslovakian Sympos. on Combinatorics, Graphs and Complexity (Prachatice, 1990) (J. Nesetril and M. Friedland, eds.), Elsevier, New York; Ann. Discrete Math. 51 (1992), 205-207. MR 1206267 (93j:05157)
  • [30] T. S. Michael and T. Quint, Sphere of influence graphs: edge density and clique size, manuscript, 1994. MR 1299482 (95i:05103)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 28A75, 05B40, 52C17

Retrieve articles in all journals with MSC: 28A75, 05B40, 52C17

Additional Information

Keywords: Besicovitch Covering Theorem, sphere packings, proximity graphs
Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society