Computing Minimum-Volume Enclosing Axis-Aligned Ellipsoids期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Computing Minimum-Volume Enclosing Axis-Aligned Ellipsoids

Authors:	P Kumar E A Yıldırım

Institution:	(1) Department of Computer Science, Florida State University, Tallahassee, FL, USA;(2) Department of Industrial Engineering, Bilkent University, Bilkent, Ankara, Turkey

Abstract:	Given a set of points $\mathcal{S}=\{x^{1},\ldots,x^{m}\}\subset \mathbb{R}^{n}$ and ε>0, we propose and analyze an algorithm for the problem of computing a (1+ε)-approximation to the minimum-volume axis-aligned ellipsoid enclosing $\mathcal{S}$ . We establish that our algorithm is polynomial for fixed ε. In addition, the algorithm returns a small core set $\mathcal{X}\subseteq \mathcal{S}$ , whose size is independent of the number of points m, with the property that the minimum-volume axis-aligned ellipsoid enclosing $\mathcal{X}$ is a good approximation of the minimum-volume axis-aligned ellipsoid enclosing $\mathcal{S}$ . Our computational results indicate that the algorithm exhibits significantly better performance than the theoretical worst-case complexity estimate. This work was supported in part by the National Science Foundation through CAREER Grants CCF-0643593 and DMI-0237415.

Keywords:	Axis-aligned ellipsoids Enclosing ellipsoids Core sets Approximation algorithms
本文献已被 SpringerLink 等数据库收录！