Symmetry-dependence in Rounding of a Convex Body
Abstract
The symmetry measure of a convex body S⊂ℝn is given by: sym(S):=max{α≥0: there exists x∈ S such that −α(S−x)⊆ S−x}, where such an x is called a Minkowski center. We prove that every convex body S admits a √(n/sym(S))-rounding of S, namely, there exists an origin-centered ellipsoid E and a center c such that E⊆ S−c⊆√(n/sym(S)) E. This result was conjectured in 2005 by Belloni and Freund. As special cases, this recovers an n-rounding of S (since sym(S)≥1/n), and a √n-rounding when sym(S)=1. In the case when S is a polytope given as the convex hull of points, the desired rounding is produced by a regularized minimum-volume covering ellipsoid problem where the regularization is with respect to the Minkowski center. Similarly, when S is a polytope given as the intersection of halfspaces, such a rounding is produced by a regularized maximum-volume inscribed ellipsoid problem. In both of these cases, the rounding can be computed by first solving a linear optimization problem (to compute sym(S) and a Minkowski center), and then solving a convex optimization problem with a logarithmic determinant objective, second-order cone constraints, and one semidefinite cone constraint. We also show that the factor √(n/sym(S)) is nearly tight in its dependence on dimension and symmetry. When (n+1)/(1+sym(S)) is an integer, we show by explicit construction that the factor √(n/sym(S)) is tight. In the more general case, for every dimension n and every admissible symmetry value, we construct a polytope S for which every rounding factor is at least √(2/3)√(n/sym(S)).
Related
- Spectral Dependence of Convex Regularization: Fundamental Limits under Right-Rotationally Invariant Designs
- Mean curvatures and symmetry of convex hypersurfaces
- One-Dimensional Symmetry Reductions of the Monge-Ampère Equation on Some Semi-Homogeneous Convex Cones in ℝ4
- Q-Edge: Symmetry-Reduced Quantum Simulation of Structured Extreme Dependence
- The Strong Mankiewicz Property for Closed Convex Body in Normed Spaces
BibTeX
@misc{xiong2026symmetrydependence,
title = {{Symmetry-dependence in Rounding of a Convex Body}},
author = {Zikai Xiong and Robert M. Freund},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.30876},
eprint = {2608.30876},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.30876},
}
RIS
TY - UNPB
TI - Symmetry-dependence in Rounding of a Convex Body
AU - Zikai Xiong
AU - Robert M. Freund
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2608.30876
UR - https://arxiv.org/abs/2608.30876
AB - The symmetry measure of a convex body S⊂ℝ^n is given by: sym(S):=max{α≥0: there exists x∈ S such that −α(S−x)⊆ S−x}, where such an x is called a Minkowski center. We prove that every convex body S admits a √(n/sym(S))-rounding of S, namely, there exists an origin-centered ellipsoid E and a center c such that E⊆ S−c⊆√(n/sym(S)) E. This result was conjectured in 2005 by Belloni and Freund. As special cases, this recovers an n-rounding of S (since sym(S)≥1/n), and a √n-rounding when sym(S)=1. In the case when S is a polytope given as the convex hull of points, the desired rounding is produced by a regularized minimum-volume covering ellipsoid problem where the regularization is with respect to the Minkowski center. Similarly, when S is a polytope given as the intersection of halfspaces, such a rounding is produced by a regularized maximum-volume inscribed ellipsoid problem. In both of these cases, the rounding can be computed by first solving a linear optimization problem (to compute sym(S) and a Minkowski center), and then solving a convex optimization problem with a logarithmic determinant objective, second-order cone constraints, and one semidefinite cone constraint. We also show that the factor √(n/sym(S)) is nearly tight in its dependence on dimension and symmetry. When (n+1)/(1+sym(S)) is an integer, we show by explicit construction that the factor √(n/sym(S)) is tight. In the more general case, for every dimension n and every admissible symmetry value, we construct a polytope S for which every rounding factor is at least √(2/3)√(n/sym(S)).
ER -