Abstract

The Chebyshev set of a bounded set K in a normed space is the set of centers of all minimal enclosing balls of K. We use the concept of ball intersection and ball hull operators to derive new properties of Chebyshev sets in normed spaces. These results give a better picture on how Chebyshev sets, ball intersections, ball hulls, and completions of bounded sets are related to each other. It is shown that the Chebyshev set of a bounded set K always contains the Chebyshev set of some completion of K. Moreover, for a special class of sets we obtain a necessary and sufficient condition that the Chebyshev set of the respective set is a singleton. We obtain new results on critical sets of Chebyshev centers, and for that purpose, surprisingly, notions from the combinatorial geometry of convex bodies play an essential role. Also we give a complete geometric description of the ball hull of a finite planar set. This can be taken as starting point for algorithmical constructions of the ball hull of such sets.

Author information

Contact details are reproduced from the original publication and may be historical.

Pedro Martín

Dep. de Matemáticas, Universidad de Extremadura, 06006 Badajoz, Spain

pjimenez@unex.es

Keywords

  • Ball hull
  • ball intersection
  • Banach space
  • Chebyshev center
  • Chebyshev set
  • complete set
  • constant width
  • Jung's constant
  • Minkowski geometry
  • normed space
  • spherical intersection property

Mathematics Subject Classification

41A50, 41A61, 46B20, 52A21

References

  1. J. Alonso, H. Martini, M. Spirova: Minimal enclosing discs, circumcircles, and circumcenters in normed planes, Part I, Comput. Geom. 45 (2012) 258–274.https://doi.org/10.1016/j.comgeo.2012.01.007Google Scholar
  2. J. Alonso, H. Martini, M. Spirova: Minimal enclosing discs, circumcircles, and circumcenters in normed planes, Part II, Comput. Geom. 45 (2012) 350–369.https://doi.org/10.1016/j.comgeo.2012.02.003Google Scholar
  3. D. Amir, Z. Ziegler: Relative Chebyshev centers in normed linear spaces I, J. Approx. Theory 29 (1980) 235–252.https://doi.org/10.1016/0021-9045(80)90129-XGoogle Scholar
  4. D. Amir, Z. Ziegler: Relative Chebyshev centers in normed linear spaces II, J. Approx. Theory 38 (1983) 293–311.https://doi.org/10.1016/0021-9045(83)90147-8Google Scholar
  5. J. Banasiak: Some contributions to the geometry of normed linear spaces, Math. Nachr. 139 (1988) 175–184.https://doi.org/10.1002/mana.19881390116Google Scholar
  6. M. Baronti, P. L. Papini: Diameters, centers and diametrically maximal sets, Rend. Circ. Mat. Palermo, Suppl. 38 (1995) 11–24.Google Scholar
  7. J. M. Borwein: Proximality and Chebyshev sets, Optim. Lett. 1 (2007) 21–32.https://doi.org/10.1007/s11590-006-0014-5Google Scholar
  8. F. Bavaud: Adjoint transform, overconvexity and sets of constant width, Trans. Amer. Math. Soc. 333 (1992) 315–324.https://doi.org/10.1090/S0002-9947-1992-1132431-9Google Scholar
  9. V. Boltyanski, H. Martini: Jung’s theorem for a pair of Minkowski spaces, Adv. Geom. 6 (2006) 645–650.https://doi.org/10.1515/ADVGEOM.2006.037Google Scholar
  10. V. Boltyanski, H. Martini, P. S. Soltan: Excursions into Combinatorial Geometry, Springer, Berlin (1997).https://doi.org/10.1007/978-3-642-59237-9Google Scholar
  11. R. Brandenberg, S. König: No dimension independent core-sets for containment under homothetics, in: Proc. Symposium on Computational Geometry (Paris, 2011), H. Ferran et al. (ed.), ACM, New York (2011) 464–471.https://doi.org/10.1145/1998196.1998272Google Scholar
  12. H. Edelsbrunner: Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical Computer Science 10, Springer, Berlin (1987).https://doi.org/10.1007/978-3-642-61568-9Google Scholar
  13. H. G. Eggleston: Sets of constant width in finite dimensional Banach spaces, Israel J. Math. 3 (1965) 163–172.https://doi.org/10.1007/BF02759749Google Scholar
  14. A. L. Garkavi: On the Čebyšev center and convex hull of a set, Usp. Mat. Nauk 19(6) (1964) 139–145 (in Russian).Google Scholar
  15. A. L. Garkavi: Minimax balayage theorem and an inscribed ball problem, Mat. Zametki 30(1) (1981) 109–121 (in Russian); Math. Notes 30(1–2) (1982) 542–548 (in English).https://doi.org/10.1007/BF01158823Google Scholar
  16. P. Gritzmann, V. Klee: Inner and outer j-radii of convex bodies in finite-dimensional normed spaces, Discrete Comput. Geom. 7 (1992) 255–280.https://doi.org/10.1007/BF02187841Google Scholar
  17. H. Groemer: On complete convex bodies, Geom. Dedicata 20 (1986) 319–334.https://doi.org/10.1007/BF00149581Google Scholar
  18. B. Grünbaum: Borsuk’s partition conjecture in Minkowski planes, Bull. Res. Council Israel, Sect. F 7 (1957) 25–30.Google Scholar
  19. B. Grünbaum: Fixing systems and inner illumination, Acta Math. Acad. Sci. Hung. 15 (1964) 161–163.https://doi.org/10.1007/BF01897033Google Scholar
  20. J. Hershberger, S. Suri: Finding tailored partitions, J. Algorithms 12 (1991) 431–463.https://doi.org/10.1016/0196-6774(91)90013-OGoogle Scholar
  21. J. Hershberger: A faster algorithm for the two-center decision problem, Inf. Process. Lett. 47 (1993) 23–29.https://doi.org/10.1016/0020-0190(93)90153-ZGoogle Scholar
  22. H. Martini, M. Spirova: On the circular hull property in normed planes, Acta Math. Hung. 125 (2009) 275–285.https://doi.org/10.1007/s10474-009-9018-9Google Scholar
  23. H. Martini, K. J. Swanepoel: The geometry of Minkowski spaces - a survey, Part II, Expo. Math. 22 (2004) 93–144.https://doi.org/10.1016/S0723-0869(04)80009-4Google Scholar
  24. H. Martini, K. J. Swanepoel, G. Weiss: The geometry of Minkowski spaces - a survey, Part I, Expo. Math. 19 (2001) 97–142.https://doi.org/10.1016/S0723-0869(01)80025-6Google Scholar
  25. J. P. Moreno: Porosity and unique completion in strictly convex spaces, Math. Z. 267 (2011) 173–184.https://doi.org/10.1007/s00209-009-0615-7Google Scholar
  26. J. P. Moreno, R. Schneider: Continuity properties of the ball hull mapping, Nonlinear Anal. 66 (2007) 914–925.https://doi.org/10.1016/j.na.2005.12.031Google Scholar
  27. J. P. Moreno, R. Schneider: Diametrically complete sets in Minkowski spaces, Israel J. Math., to appear.Google Scholar
  28. J. P. Moreno, R. Schneider: Local Lipschitz continuity of the diametric completion mapping, Houston J. Math. 38 (2012) 1207–1223.Google Scholar
  29. M. A. Perles, H. Martini, Y. S. Kupitz: Ball polytopes and the Vászonyi problem, Acta Math. Hung. 126 (2009) 99–163.https://doi.org/10.1007/s10474-009-9030-0Google Scholar
  30. T. S. S. R. K. Rao: Chebyshev centers and centrable sets, Proc. Amer. Math. Soc. 130 (2002) 2593–2598.https://doi.org/10.1090/S0002-9939-02-06624-8Google Scholar
  31. M. Sharir: A near-linear algorithm for the planar 2-center problem, Discrete Comput. Geom. 18 (1997) 125–134.https://doi.org/10.1007/PL00009311Google Scholar
  32. M. Spirova: Discrete Geometry in Normed Spaces, Südwestdeutscher Verlag für Hochschulschriften, Saarbrücken (2011).Google Scholar
  33. P. Terán: Intersections of balls and the ball hull mapping, J. Convex Analysis 17 (2010) 277–292.https://doi.org/10.68381/jca17020Google Scholar

Suggested citation

P. Martín, H. Martini, M. Spirova. “Chebyshev Sets and Ball Operators.” Journal of Convex Analysis 21 (2014), No. 3, 601–618. https://doi.org/10.68381/jca21032

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2014. Rights now held by Banach Press LLC.