×

Minimum-volume enclosing ellipsoids and core sets. (English) Zbl 1093.90039

Summary: We study the problem of computing a \((1+\varepsilon)\)-approximation to the minimum-volume enclosing ellipsoid of a given point set \(\mathcal S = \{p^1,p^2,\dots,p^n\} \subseteq \mathbb R^d\). Based on a simple, initial volume approximation method, we propose a modification of the Khachiyan first-order algorithm. Our analysis leads to a slightly improved complexity bound of \(O(nd^3/\varepsilon)\) operations for \(\varepsilon \in (0,1)\). As a byproduct, our algorithm returns a core set \(\mathcal X \subseteq \mathcal S\) with the property that the minimum-volume enclosing ellipsoid of \(\mathcal X\) provides a good approximation to that of \(\mathcal S\). Furthermore, the size of \(\mathcal X\) depends on only the dimension \(d\) and \(\varepsilon\), but not on the number of points \(n\). In particular, our results imply that \(| \mathcal X| = O(d^2/\varepsilon)\) for \(\varepsilon \in (0,1)\).

MSC:

90C25 Convex programming
90C05 Linear programming
68W25 Approximation algorithms

Software:

MVE
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[4] Chazelle B., Matoušek J. On Linear Time Deterministic Algorithms for Optimization Problems in Fixed Dimension, ACM-SIAM Symposium on Discrete Algorithms, 281–290, (1993) · Zbl 0808.90090
[8] Bouville C. (1985). Bounding Ellipsoid for Ray-Fractal Intersection. Proceedings of the 12th Annual Conference on Computer Graphics and Interative Techniques. 19: 45–52
[12] Comaniciu D., Meer P. (1997). Robust Analysis of Feature Spaces: Color Image Segmentation. IEEE Conference on Computer Vision and Pattern Recognition. 750–755
[14] Knorr E.M., Ng R.T., Zamar R.H. (2001). Robust Space Transformations for Distance-Based Operations. Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 126–135
[15] John F. (1985). Extremum Problems with Inequalities as Subsidiary Conditions, Studies and Essays in Honor of R. Courant, Wiley, Interscience, New York, NY, 187–204, 1948 (see also Fritz John, Collected Papers, Edited by J. Moser, Birkhäuser, Boston, Massachusetts, 2, pp 543–560
[19] Sun P., Freund R.M. (2004). Computation of Minimum-Volume Covering Ellipsoids, Operations Research · Zbl 1165.90571
[20] Matoušek J., Sharir M., Welzl E. (1992). A Subexponential Bound for Linear Programming. Proceedings of the 8th Annual Symposium on Computational Geometry, 1–8
[22] Gärtner B., Schönherr S. (1997). Exact Primitives for Smallest Enclosing Ellipses. Proceedings of the 13th Annual ACM Symposium on Computational Geometry, 430–432
[30] BĂdoiu M., Har-Peled S., Indyk P. (2002). Approximate Clustering via Core Sets, Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 250–257 · Zbl 1192.68871
[31] BĂdoiu M., Clarkson K.L. (2003). Smaller Core Sets for Balls, Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms. 801–802 · Zbl 1092.68660
[32] Kumar P., Mitchell J.S.B., Yildirim E.A. (2003). Approximate Minimum Enclosing Balls in High Dimensions Using Core Sets. ACM Journal of Experimental Algorithmics (online), 8 · Zbl 1083.68138
[33] Chan T.M. (2004). Faster Core Set Constructions and Data-Stream Algorithms in Fixed Dimensions. Proceedings of the 20th Annual ACM Symposium on Computational Geometry, 152–159 · Zbl 1377.68322
[34] Aggarwal P.K., Poreddy R., Varadarajan K.R., Yu H. (2004). Practical Methods for Shape Fitting and Kinetic Data Structures Using Core Sets, Proceedings of the 20th Annual ACM Symposium on Computational Geometry, 263–272 · Zbl 1375.68173
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.