Abstract
We study the smallest number ψ(K) such that a given convex bodyK in ℝn can be cut into two partsK 1 andK 2 by a surface with an (n−1)-dimensional measure ψ(K) vol(K 1)·vol(K 2)/vol(K). LetM 1(K) be the average distance of a point ofK from its center of gravity. We prove for the “isoperimetric coefficient” that
, and give other upper and lower bounds. We conjecture that our upper bound is the exact value up to a constant.
Our main tool is a general “Localization Lemma” that reduces integral inequalities over then-dimensional space to integral inequalities in a single variable. This lemma was first proved by two of the authors in an earlier paper, but here we give various extensions and variants that make its application smoother. We illustrate the usefulness of the lemma by showing how a number of well-known results can be proved using it.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles and news from researchers in related subjects, suggested using machine learning.Avoid common mistakes on your manuscript.
References
D. Applegate and R. Kannan (1990): Sampling and integration of near log-concave functions,Proc. 23th ACM Symposium on the Theory of Computing, pp. 156–163.
J. Bokowski (1980): Ungleichungen für des Inhalt von Trennflächen,Arch. Math. 34, 84–89.
J. Bokowski and E. Spencer Jr. (1979): Zerlegung Konvexen Körperdurch minimale Trennflächen,J. Reine Angew. Math. 311–312, 80–100.
C. Borell (1975): The Brunn-Minkowski inequality in Gauss spaces,Invent. Math. 30, 207–216.
J. Bourgain (1991):On the Distribution of Polynomials on High Dimensional Convex Sets, Lecture Notes in Mathematics, Vol. 1469, Springer-Verlag, Berlin, pp. 127–137.
A. Dinghas (1957): Über eine Klasse superadditiver Mengenfunktionale von Brunn-Minkowski-Lusternik-schem Typus,Math. Z. 68, 111–125.
M. Dyer and A. Frieze (1992): Computing the volume of convex bodies: a case where randomness provably helps, in:Probabilistic Combinatorics and Its Applications (ed. B. Bollobás), Proceedings of Symposia in Applied Mathematics, Vol. 44, American Mathematical Society, Providence, RI, pp. 123–170.
M. Dyer, A. Frieze, and R. Kannan (1989): A random polynomial time algorithm for approximating the volume of convex bodies,Proc. 21st ACM Symposium on Theory of Computing, pp. 375–381.
M. Gromov and V. D. Milman (1984): Brunn theorem and a concentration of volume of convex bodies, GAFA Seminar Notes, Tel Aviv University.
D. Hensley (1980): Slicing convex bodies and bounds on the slice area in terms of the body's covariance,Proc. Amer. Math. Soc. 79, 619–625.
F. John (1948): Extermum problems with inequalities as subsidiary conditions, in:Studies and Essays Presented to R. Courant, Interscience, New York, pp. 187–204.
A. Karzanov and L. G. Khachiyan (1991), On the conductance of order Markov chains,Order 8, 7–15.
L. Lovász and M. Simonovits (1990): Mixing rate of Markov chains, an isoperimetric inequality, and computing the volume.Proc. 31st IEEE Symposium on Foundations of Computer Science, pp. 346–355.
L. Lovász and M. Simonovits (1993): Random walks in a convex body and an improved volume algorithm,Random Structures Algebra 4, 359–412.
V. D. Milman and A. Pajor (1989): Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normedn-dimensional space, in:Geometric Aspects of Functional Analysis (eds. J. Lindenstrauss and V. D. Milman), Lecture Notes in Mathematics, Vol. 1376, Springer-Verlag, Berlin, pp. 64–104.
A. Prékopa (1971): Logarithmic concave measures with applications to stochastic programming,Acta Sci. Math. (Szeged.) 32, 301–316.
G. Sonnevend (1989): Applications of analytic centers for the numerical solution of semi-infinite, convex programs arising in control theory, DFG Report No. 170/1989, Institut für angew. Mathematik, University of Würzburg.
Author information
Authors and Affiliations
Additional information
The work of R. Kannan was done while visiting Yale University and was supported by NSF Grant CCR-9208597 to Carnegie-Mellon. The work of László Lovász was supported by NSF Grant CCR-9402916.
Rights and permissions
About this article
Cite this article
Kannan, R., Lovász, L. & Simonovits, M. Isoperimetric problems for convex bodies and a localization lemma. Discrete Comput Geom 13, 541–559 (1995). https://doi.org/10.1007/BF02574061
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02574061