Minimum Volume Enclosing Ellipsoid

version 1.2.0.0 (2.05 KB) by Nima Moshtagh
Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space.

10.4K Downloads

Updated 20 Jan 2009

View License

[A , c] = MinVolEllipse(P, tolerance)

Finds the minimum volume enclosing ellipsoid (MVEE) of a set of data points stored in matrix P. The following optimization problem is solved:

minimize log(det(A))
s.t. (P_i - c)'*A*(P_i - c)<= 1

in variables A and c, where P_i is the i-th column of the matrix P.
The solver is based on Khachiyan Algorithm, and the final solution is different from the optimal value by the pre-specified amount of 'tolerance'.
---------------------------
Outputs:

c : D-dimensional vector containing the center of the ellipsoid.

A : This matrix contains all the information regarding the shape of the ellipsoid. To get the radii and orientation of the ellipsoid take the Singular Value Decomposition ( svd function in matlab) of the output matrix A:

[U Q V] = svd(A);

the radii are given by:

r1 = 1/sqrt(Q(1,1));
r2 = 1/sqrt(Q(2,2));
...
rD = 1/sqrt(Q(D,D));

and matrix V is the rotation matrix that gives you the orientation of the ellipsoid.

For plotting in 2D or 3D, use MinVolEllipse_plot.m (see the link bellow)

Cite As

Nima Moshtagh (2022). Minimum Volume Enclosing Ellipsoid (https://www.mathworks.com/matlabcentral/fileexchange/9542-minimum-volume-enclosing-ellipsoid), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R13
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!