Computing minimum-volume enclosing axis-aligned ellipsoids (Q2481119)

The paper is concerned with the presentation and the analysis of a polynomial algorithm which delivers an approximation of the minimum-volume axis-aligned ellipsoid (MVAE) that encloses a set \(S\) of \(m\) points in \(\mathbb{R}^{n}\). The computation of such ellipsoids is useful, for example, in connection with real time computer graphics and computer gaming and with machine learning applications. The proposed algorithm also generates a small so-called core set \(X\subseteq S\) of \(S\) whose size is independent of the number \(m\) of points forming \(S\) and for which the enclosing MVAE is a good approximation of the MVAE enclosing \(S\). It is illustrated by examples and computational results that the theoretical worst-case complexity estimates derived for the given algorithm cannot be improved, but are rather pessimistic in general.