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

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claims
RedirectionBot (talk | contribs)
Changed an Item
Property / author
 
Property / author: Ji{ří} Matoušek / rank
 
Normal rank
Property / reviewed by
 
Property / reviewed by: Marek Lassak / rank
 
Normal rank

Revision as of 04:22, 10 February 2024

scientific article
Language Label Description Also known as
English
Improved upper bounds for approximation by zonotopes
scientific article

    Statements

    Improved upper bounds for approximation by zonotopes (English)
    0 references
    5 November 1997
    0 references
    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.
    0 references
    approximation
    0 references
    zonotope
    0 references
    zonoid
    0 references
    polynomial-time deterministic algorithm
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references