Geodesic
Goffin's algorithm for zonotopes
Kybernetika, Tome 48 (2012) no. 5, pp. 890-906.

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

The Löwner-John ellipse of a full-dimensional bounded convex set is a circumscribed ellipse with the property that if we shrink it by the factor $n$ (where $n$ is dimension), we obtain an inscribed ellipse. Goffin's algorithm constructs, in polynomial time, a tight approximation of the Löwner-John ellipse of a polyhedron given by facet description. In this text we adapt the algorithm for zonotopes given by generator descriptions. We show that the adapted version works in time polynomial in the size of the generator description (which may be superpolynomially shorter than the facet description).
Classification : 52B12, 52B55, 68U05, 90C57
Keywords: Löwner–John ellipse; zonotope; Goffin's algorithm; ellipsoid method 
@article{KYB_2012__48_5_a4,
     author = {\v{C}ern\'y, Michal},
     title = {Goffin's algorithm for zonotopes},
     journal = {Kybernetika},
     pages = {890--906},
     publisher = {mathdoc},
     volume = {48},
     number = {5},
     year = {2012},
     mrnumber = {3086858},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2012__48_5_a4/}
}
TY  - JOUR
AU  - Černý, Michal
TI  - Goffin's algorithm for zonotopes
JO  - Kybernetika
PY  - 2012
SP  - 890
EP  - 906
VL  - 48
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/KYB_2012__48_5_a4/
LA  - en
ID  - KYB_2012__48_5_a4
ER  - 
%0 Journal Article
%A Černý, Michal
%T Goffin's algorithm for zonotopes
%J Kybernetika
%D 2012
%P 890-906
%V 48
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/KYB_2012__48_5_a4/
%G en
%F KYB_2012__48_5_a4
Černý, Michal. Goffin's algorithm for zonotopes. Kybernetika, Tome 48 (2012) no. 5, pp. 890-906. http://geodesic.mathdoc.fr/item/KYB_2012__48_5_a4/