Published in

2008 International Conference on Computational Sciences and Its Applications

DOI: 10.1109/iccsa.2008.24

Links

Tools

Export citation

Search in Google Scholar

A Note on Approximate Minimum Volume Enclosing Ellipsoid of Ellipsoids

Proceedings article published in 2008 by Sachin Jambawalikar ORCID, Piyush Kumar
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Green circle
Postprint: archiving allowed
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

We study the problem of computing the minimum volume enclosing ellipsoid (MVEE) containing a given set of ellipsoids S = {E1, E2, hellip, En} sube Ropfd. We show how to efficiently compute a small set X sube S of size at most a = |X| = O(d2/epsi ) whose minimum volume ellipsoid is an (1 + epsi)-approximation to the minimum volume ellipsoid of S. We use an augmented real num ber model of computation to achieve a running time of O(alpha(ndomega + d3)) where omega < 2.376 is the exponent of square matrix multiplication. This is the best known complexity for solving the MVEE problem when n Gt d and e is large. The algorithm is built on the previous work by Kumar and Yrfdirim [17].