Abstract
This paper is concerned with the various inner and outer radii of a convex bodyC in ad-dimensional normed space. The innerj-radiusr j (C) is the radius of a largestj-ball contained inC, and the outerj-radiusR j (C) measures how wellC can be approximated, in a minimax sense, by a (d —j)-flat. In particular,r d (C) andR d (C) are the usual inradius and circumradius ofC, while 2r 1(C) and 2R 1(C) areC's diameter and width.
Motivation for the computation of polytope radii has arisen from problems in computer science and mathematical programming. The radii of polytopes are studied in [GK1] and [GK2] from the viewpoint of the theory of computational complexity. This present paper establishes the basic geometric and algebraic properties of radii that are needed in that study.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
H. Bauer, Minimalstellen von Funktionen und Extremalpunkte,Archiv. Math. 9 (1958), 389–393.
W. Blaschke,Kreis und Kugel, Veit, Leipzig, 1916; second edn., W. de Gruyter, Berlin.
H. L. Bodlaender, P. Gritzmann, V. Klee, and J. Van Leeuwen, Computational complexity of norm-maximization,Combinatorica 10 (1990), 203–225.
H. F. Bohnenblust, Convex regions and projections in Minkowski spaces,Ann. of Math. 39 (1938), 301–308.
T. Bonnesen and W. Fenchel,Theorie der konvexen Körper, Springer-Verlag, Berlin, 1934.
A. L. Brown, Bestn-dimensional approximation to sets of functions,Proc. London Math. Soc. 14 (1964), 577–594.
L. Danzer, B. Grünbaum, and V. Klee, Helly's theorem and its relatives. InConvexity (V. Klee, ed.), Proc. Symp. Pure Math., Vol. 13, American Mathematical Society, Providence, RI, 1963, pp. 101–180.
M. M. Day, Some characterizations of inner-product spaces,Trans. Amer. Math. Soc. 62 (1947), 320–337.
J. Eckhoff, Transversalprobleme vom Gallaischen Typ, Ph.D.Thesis, Universität Göttingen, 1969.
H. G. Eggleston,Convexity, Cambridge University Press, Cambridge, 1958, 1969.
H. G. Eggleston, Notes on Minkowski geometry (I): Relations between the circumradius, diameter, inradius, and minimal width of a convex set,J. London Math. Soc. 33 (1958), 76–81.
P. Erdös, On sets of distances ofn points,Amer. Math. Monthly 53 (1946), 248–250.
P. Erdös, On sets of distances of points in Euclidean space,Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 165–169.
A. L. Garkavi, On the Cebysev center and convex hull of a set,Uspekhi Mat. Nauk 19 (1964), 139–145.
P. Gritzmann, L. Habsieger, and V. Klee, Good and bad radii of convex polygons,SIAM J. Comput.,20 (1991), 395–403.
P. Gritzmann and V. Klee, Computational complexity of the inner and outerj-radii of polytopes in finite-dimensional normed spaces,Math. Programming, to appear.
P. Gritzmann and V. Klee, On the error of polynomial computations of width and diameter, in preparation.
P. Gritzmann and M. Lassak, Estimates for the minimal width of polytopes inscribed in convex bodies,Discrete Comput. Geom. 4 (1989), 627–635.
M. Grötschel, L. Lovász, and A. Schrijver,Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin, 1988.
B. Grünbaum, A proof of Vazsonyi's conjecture,Bull. Res. Council Israel Sect. A 6 (1956), 77–78.
E. Helly, Über Mengen konvexer Körper mit gemeinschaftlichen Punkten,Jahresber. Deutsch. Math.-Verein. 32 (1923), 175–176.
A. Heppes, Beweis einer Vermutung von A. Vázsonyi,Acta Math. Acad. Sci. Hungar. 7 (1956), 463–466.
H. W. E. Jung, Über die kleinste Kugel die eine räumliche Figur einschließt,J. Reine Angew. Math. 123 (1901), 241–257.
S. Kakutani, Some characterizations of Euclidean space,Japan. J. Math. 16 (1939), 93–97.
V. Klee, Circumspheres and inner products,Math. Scand. 8 (1960), 363–370.
V. Klee, E. Maluta, and C. Zanco, Inspheres and inner products,Israel J. Math. 55 (1986), 1–14.
A. Kolmogoroff, Über die beste Annäherung von Funktionen einer gegebenen Funktionklasse,Ann. of Math. 37 (1936), 107–110.
K. Leichtweiss, Zwei Extremalprobleme der Minkowski-Geometrie,Math. Z. 62 (1955), 37–49.
G. G. Lorentz,Approximation of Functions, Holt, Rinehart, and Winston, New York, 1966.
I. G. Macdonald, Regular simplices with integral vertices,C. R. Math. Rep. Acad. Sci. Canada 9 (1987), 189–193.
B. B. Panda and O. P. Kapoor, On equidistant sets in normed linear spaces,Bull. Austral. Math. Soc. 11 (1974), 443–454.
M. J. Pelling, Regular simplices with rational vertices,Bull. London Math. Soc. 9 (1977), 199–200.
G. Y. Perelman, On thek-radii of a convex body,Sibirsk. Mat. Zh. 28 (1987), 185–186 (in Russian).
A. Pinkus,n-Widths in Approximation Theory, Springer-Verlag, Berlin, 1985.
F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985.
C. A. Rogers and G. C. Shephard, The difference body of a convex body,Arch. Math. 8 (1957), 220–233.
I. J. Schoenberg, Regular simplices and quadratic forms,J. London Math. Soc. 12 (1937), 48–55.
I. Singer,Best Approximation in Normed Linear Spaces by Elements of Linear Subspaces, Springer-Verlag, New York, 1970.
P. Steinhagen, Über die größte Kugel in einer konvexen Punktmenge,Abh. Math. Sem. Univ. Hamburg 1 (1921), 15–26.
S. Straszewicz, Sur un problème géometrique de P. Erdös,Bull. Acad. Polon. Sci. Cl. III 5 (1957), 39–40.
V. M. Tihomirov, Diameters of sets in functional spaces and the theory of best approximation,Russian Math. Surveys 15 (1960), 75–111; translated fromUspekhi Mat. Nauk 15 (1960), 81–120.
V. M. Tihomirov,Some Questions in Approximation Theory, Izdat. Moskov. Univ., Moscow, 1974 (in Russian).
A. C. Yao, On constructing minimum spanning trees ink-dimensional space and related problems,SIAM J. Comput. 11 (1982), 721–736.
Author information
Authors and Affiliations
Additional information
Much of this paper was written when both authors were visiting the Institute for Mathematics and Its Applications, 206 Church Street S.E., Minneapolis, MN 55455, USA. The research of P. Gritzmann was supported in part by the Alexander-von-Humboldt Stiftung and the Deutsche Forschungsgemeinschaft. V. Klee's research was supported in part by the National Science Foundation.
Rights and permissions
About this article
Cite this article
Gritzmann, P., Klee, V. Inner and outerj-radii of convex bodies in finite-dimensional normed spaces. Discrete Comput Geom 7, 255–280 (1992). https://doi.org/10.1007/BF02187841
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187841