Algorithms for polyhedral approximation of multidimensional ellipsoids

We present efficient and simple algorithms far the approximation of a d-dim ansional ellipsoid by polytopes of a prescribed size which are either conta ined in or contain the ellipsoid. The polytopes provided by our algorithms have a high degree of regularity, which enables us to construct their j-ske letons, j = 0,..., d - 1, efficiently. The rate of approximation, as measur ed by the symmetric distance and up to a constant, is best possible by any algorithm. (C) 1999 Academic Press.