Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-26T17:52:53.378Z Has data issue: false hasContentIssue false
  • English
  • Français

SHARPENING GEOMETRIC INEQUALITIES USING COMPUTABLE SYMMETRY MEASURES

Part of: General convexity

Published online by Cambridge University Press:  05 December 2014

René Brandenberg  and
Stefan König
René Brandenberg
Affiliation:
Zentrum Mathematik, Technische Universität München, Boltzmannstr. 3, 85747 Garching bei München, Germany email [email protected]
Stefan König
Affiliation:
Institut für Mathematik, Technische Universität Hamburg-Harburg, Schwarzenbergstr. 95, 21073 Hamburg, Germany email [email protected]
Get access

Abstract

Many classical geometric inequalities on functionals of convex bodies depend on the dimension of the ambient space. We show that this dimension dependence may often be replaced (totally or partially) by different symmetry measures of the convex body. Since these coefficients are bounded by the dimension but possibly smaller, our inequalities sharpen the original ones. Since they can often be computed efficiently, the improved bounds may also be used to obtain better bounds in approximation algorithms.

MSC classification

Primary: 52A40: Inequalities and extremum problems
Type
Research Article
Information
Mathematika , Volume 61 , Issue 3 , September 2015 , pp. 559 - 580
Copyright
Copyright © University College London 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alexander, R., The width and diameter of a simplex. Geom. Dedicata 6(1) 1977, 87–94.CrossRefGoogle Scholar
Ball, K., Ellipsoids of maximal volume in convex bodies. Geom. Dedicata 41(2) 1992, 241–250.CrossRefGoogle Scholar
Ball, K., An elementary introduction to modern convex geometry. In Flavors of Geometry, Cambridge University Press (Cambridge, 1997), 1–58.Google Scholar
Belloni, A. and Freund, R. M., On the symmetry function of a convex set. Math. Program. 111(1–2) 2008, 57–93.CrossRefGoogle Scholar
Betke, U. and Henk, M., Estimating sizes of a convex body by successive diameters and widths. Mathematika 39(2) 1992, 247–257.CrossRefGoogle Scholar
Bohnenblust, H. F., Convex regions and projections in Minkowski spaces. Ann. of Math. (2) 39(2) 1938, 301–308.CrossRefGoogle Scholar
Boltyanski, V. and Martini, H., Jung’s theorem for a pair of Minkowski spaces. Adv. Geom. 6(4) 2006, 645–650.CrossRefGoogle Scholar
Bonnesen, T. and Fenchel, W., Theorie der Konvexen Körper, Springer (Berlin, 1974) . Engl. transl. in Theory of Convex Bodies, BCS Associates (Moscow, ID, 1987).Google Scholar
Böröczky, K. Jr, Hernández Cifre, M. and Salinas, G., Optimizing area and perimeter of convex sets for fixed circumradius and inradius. Monatsh. Math. 138(2) 2003, 95–110.CrossRefGoogle Scholar
Bottema, O., Djordjevic, R. Z., Janic, R. R., Mitrinović, D. S. and Vasić, P. M., Geometric Inequalities, Wolters-Noordhoff (Groningen, The Netherlands, 1969).Google Scholar
Brandenberg, R., Dattasharma, A., Gritzmann, P. and Larman, D., Isoradial bodies. Discrete Comput. Geom. 32(4) 2004, 447–457.CrossRefGoogle Scholar
Brandenberg, R. and König, S., No dimension-independent core-sets for containment under homothetics. Discrete Comput. Geom. 49(1) 2013, 3–21 (Special Issue on SoCG ’11).CrossRefGoogle Scholar
Brandenberg, R. and Roth, L., New algorithms for k-center and extensions. J. Comb. Optim. 18(4) 2009, 376–392.CrossRefGoogle Scholar
Brandenberg, R. and Roth, L., Minimal containment under homothetics: a simple cutting plane approach. Comput. Appl. 48(2) 2011, 325–340.CrossRefGoogle Scholar
Brieden, A., Geometric optimization problems likely not contained in APX. Discrete Comput. Geom. 28(2) 2002, 201–209.CrossRefGoogle Scholar
Danzer, L., Grünbaum, B. and Klee, V., Helly’s Theorem and its relatives. In Convexity (Proceedings of Symposia in Pure Mathematics 7) (ed. Klee, V.), American Mathematical Society (1963), 101–180.CrossRefGoogle Scholar
Eaves, B. C. and Freund, R. M., Optimal scaling of balls and polyhedra. Math. Program. 23(1) 1982, 138–147.CrossRefGoogle Scholar
Eggleston, H. G., Convexity, Vol. 47. Cambridge University Press (Cambridge, New York, 1958).CrossRefGoogle Scholar
Fejes Tóth, L., Lagerungen in der Ebene auf der Kugel und im Raum, Springer (Berlin, Heidelberg, 1953).Google Scholar
Freund, R. M. and Orlin, J. B., On the complexity of four polyhedral set containment problems. Math. Program. 33(2) 1985, 139–145.CrossRefGoogle Scholar
Gonzáles Merino, B., On the ratio between successive radii of a symmetric convex body. Math. Inequal. Appl. 16(2) 2013, 569–576.Google Scholar
Gritzmann, P. and Klee, V., Inner and outer j-radii of convex bodies in finite-dimensional normed spaces. Discrete Comput. Geom. 7(1) 1992, 255–280.CrossRefGoogle Scholar
Gritzmann, P. and Klee, V., Computational complexity of inner and outer j-radii of polytopes in finite-dimensional normed spaces. Math. Program. 59(1) 1993, 163–213.CrossRefGoogle Scholar
Gritzmann, P. and Lassak, M., Estimates for the minimal width of polytopes inscribed in convex bodies. Discrete Comput. Geom. 4(1) 1989, 627–635.CrossRefGoogle Scholar
Gruber, P. and Schuster, F., An arithmetic proof of John’s ellipsoid theorem. Arch. Math. 85(1) 2005, 82–88.CrossRefGoogle Scholar
Grünbaum, B., Measures of symmetry for convex sets. In Convexity: Proceedings of Symposia in Pure Mathematics, Vol. 7 (ed. Klee, V.), American Mathematical Society (Providence, RI, 1963), 271–284.CrossRefGoogle Scholar
Guo, Q. and Kaijser, S., On the distance between convex bodies. Northeastern Math. J. 5(3) 1999, 323–331.Google Scholar
Hadwiger, H., Vorlesungen über Inhalt, Oberfläche und Isoperimetrie, Springer (Berlin, Heidelberg, 1957).CrossRefGoogle Scholar
Henk, M., A generalization of Jung’s Theorem. Geom. Dedicata 42(2) 1992, 235–240.CrossRefGoogle Scholar
Henk, M., Löwner–John ellipsoids. In Optimization Stories (Documenta Mathematica, Extra Volume ISMP (2012)) (ed. Grötschel, M.), Deutsche Mathematiker-Vereinigung (Berlin, 2012), 95–106.CrossRefGoogle Scholar
Henk, M. and Hernández Cifre, M., Intrinsic volumes and successive radii. J. Math. Anal. Appl. 343(2) 2008, 733–742.CrossRefGoogle Scholar
Hernández Cifre, M., Salinas, G., Pastor, J. A. and Segura, S., Complete systems of inequalities for centrally symmetric convex sets in the n-dimensional space. Arch. Inequal. Appl. 1 2003, 155–167.Google Scholar
John, F., Extremum problems with inequalities as subsidiary conditions. In Studies and Essays: Presented to R. Courant on His 60th Birthday, January 8, 1948, Interscience (New York, 1948), 187–204.Google Scholar
Jung, H. W. E., Über die kleinste Kugel, die eine räumliche Figur einschließt. J. Reine Angew. Math. 123 1901, 241–257.Google Scholar
Kaijser, S. and Guo, Q., Approximations of convex bodies by convex bodies. Northeastern Math. J. 19(4) 2003, 323–332.Google Scholar
Khachiyan, L. G. and Todd, M. J., On the complexity of approximating the maximal inscribed ellipsoid for a polytope. Math. Program. 61(1) 1993, 137–159.CrossRefGoogle Scholar
Knauer, C., König, S. and Werner, D., Fixed parameter complexity of norm maximization. Preprint, 2013, arXiv:1307.6414.Google Scholar
Leichtweiss, K., Zwei Extremalprobleme der Minkowski-Geometrie. Math. Z. 62(1) 1955, 37–49.CrossRefGoogle Scholar
Perel’man, G. Y., k-radii of a convex body. Sib. Math. J. 28(4) 1987, 665–666.CrossRefGoogle Scholar
Schneider, R., Convex bodies: The Brunn–Minkowski Theory, Cambridge University Press (Cambridge, New York, 1993).CrossRefGoogle Scholar
Schneider, R., Stability for some extremal properties of the simplex. J. Geom. 96(1) 2009, 135–148.CrossRefGoogle Scholar
Scott, P. R. and Awyong, P. W., Inequalities for convex sets. J. Inequal. Pure Appl. Math. 1(1) 2000, 1–13.Google Scholar
Steinhagen, P., Über die größte Kugel in einer konvexen Punktmenge. Abh. Math. Semin. Univ. 1(1) 1922, 15–26.CrossRefGoogle Scholar
Todd, M. J. and Yıldırım, E. A., On Khachiyan’s algorithm for the computation of minimum-volume enclosing ellipsoids. Discrete Appl. Math. 155(13) 2007, 1731–1744.CrossRefGoogle Scholar