Nearly-Tight Bounds for Zonotope Containment and Beyond
This work provides tight bounds and algorithms for convex body containment problems, which are fundamental in optimization and geometry, with implications for approximating convex bodies by polytopes.
The paper presents a nearly-tight approximation algorithm for zonotope containment, achieving an O(√d)-approximation that almost matches the Ω(√(d/log d)) lower bound, and proves Talagrand's conjecture for Δ-modular zonotopes with constant Δ, linking zonoid sparsification to spectral sparsification.
We investigate the convex-body containment problem $\max\{s >0 : s Z \subseteq Q\}$, where the outer body $Q \subseteq \mathbb R^d$ is described by a membership oracle and the inner body $Z \subseteq \mathbb R^d$ is a zonotope. Our main result is a sampling-based $O(\sqrt{d})$-approximation algorithm for this problem that almost matches the lower bound of $Ω(\sqrt{d/\log d})$ by Khot and Naor in the oracle model. Assuming zonotopes can be sparsified by a linear number of generators, which is referred to as Talagrand conjecture, our approach attains the optimal approximation factor of $Θ(\sqrt{d/\log d})$. Our second main result is a proof of Talagrand's conjecture for $Δ$-modular zonotopes whenever $Δ$ is constant. Those zonotopes are of the form $Z = \{ Wx \colon \| x\|_\infty \leq 1\}$ where the non-zero $d \times d$ sub-determinants of $W$ are between $1$ and $Δ$. This result establishes a connection between zonoid sparsification and spectral sparsification of Batson, Spielman and Srivastava. We complement these results with a universal $Ω(\sqrt{d/\log d})$ lower bound holding for all zonotopes. Finally, we consider containment problems $\max\{s >0 : s K \subseteq Q\}$, for general convex bodies $K \subseteq \mathbb R^d$. A result of Naszódi on approximating $K \subseteq \mathbb R^d$ by a polytope implies a $Θ(d/\log d)$ approximation algorithm in polynomial time. We show the tightness of this approximation factor in the oracle model via a reduction to the circumradius computation. Our lower bound holds for centrally symmetric convex sets, implying that Barvinok's optimal $O(\sqrt{d})$-approximation of a centrally symmetric convex body by a polytope with a polynomial number of vertices cannot be computed in polynomial time.