Improved upper bounds for approximation by zonotopes (Q1373005): Difference between revisions

We say that a zonotope \(A\) approximates a zonoid \(Z\) (both with centers in the origin of \(n\)-space \(\mathbb{R}^n)\) with error at most \(\varepsilon\) provided \(Z\subset A\subset (1+ \varepsilon)Z\). The author proves that there exists a constant \(C\) which depends only on \(n\) such that arbitrary zonoid in \(\mathbb{R}^n\), where \(n\geq 5\), can be approximated up to error \(\varepsilon\) by a zonotope whose number of summands of equal lengths is at most \(C\varepsilon^{-2 +6/(n+2)}\). Moreover, there is a constant \(C=C(n)\) such that arbitrary zonoid in \(\mathbb{R}^n\), where \(n\geq 3\), can be approximated up to error \(\varepsilon\) by a zonotopy whose number of summands (not necessarily of equal lengths) is at most \(C\varepsilon^{-2+ 6/(n+2)} (\log 1/ \varepsilon)^{1-3/(n+2)}\). This zonotope can be found by a polynomial-time deterministic algorithm.