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).
Löwner-John ellipse, zonotope, Goffin's algorithm, ellipsoid method
90C57, 52B12, 52B55, 68U05