Search Comments and Ratings

go

   
Date File Comment by Comment Rating
14 Aug 2014 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh David

Hmmm....
det(A) = pi^2 / area^2,

so it seems the optimization for minimum area is to maximize, rather than minimize, log(det(A)).

Also, for small d, it may be easier to obtain semi major/minor lengths (a, b) by finding the eigenvalues/vectors of A (eigenvalues are 1/a^2, 1/b^2, etc, rotation matrix columns are the eigenvectors).

I'm finding this algorithm gives me det(A) < 0 (a hyperbola) for some point sets. Also, A should be invariant under translation of all the input points (which should just result in a translation of c), but I find it is quite sensitive.

12 Jun 2014 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh Anton Semechko

sweet, thanks!

10 Jun 2014 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh Pengju

28 Aug 2013 Plot an ellipse in "center form" Draws 2D and 3D ellipses that are given in "center form". Author: Nima Moshtagh lan

wonderful!!

17 Mar 2013 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh Javier

Hi,

thanks for sharing the code it's really good. One question, please could you explain me which it's the differente between this method and least squares?

Thank you very much

11 Jun 2012 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh banjo

thanks. This is good.

08 Mar 2012 Plot an ellipse in "center form" Draws 2D and 3D ellipses that are given in "center form". Author: Nima Moshtagh Sepehr Farhand

08 Mar 2012 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh Sepehr Farhand

15 Nov 2011 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh Glib

12 Oct 2011 Plot an ellipse in "center form" Draws 2D and 3D ellipses that are given in "center form". Author: Nima Moshtagh Kwame

Can you please show me an example of the function inputs? I keep getting errors about my inputs.

06 Sep 2011 Plot an ellipse in "center form" Draws 2D and 3D ellipses that are given in "center form". Author: Nima Moshtagh Ahmed Fasih

To plot just circles with "r" radius, pass in eye(2)*(r)^-2 as the covariance matrix. A plot function like this shouldn't change the plot more than it needs to: I disabled the "grid" and "axis" commands. It should also return handles to the plot objects it creates: I had to add this as well. But this code gets me 95% there, thanks.

20 Aug 2011 Plot an ellipse in "center form" Draws 2D and 3D ellipses that are given in "center form". Author: Nima Moshtagh LIAO xj

18 Feb 2011 Regular Polygons Plots the regular polygon {N/d} with vertices on a circle of radius 'rad'. Author: Nima Moshtagh laleh

14 Dec 2010 Plot an ellipse in "center form" Draws 2D and 3D ellipses that are given in "center form". Author: Nima Moshtagh Jimmy

Error appears when I use your function.
I found that there is another ellipsoid.m in my external toolbox.
Maybe this ellipsoid.m is called instead of that in Matlab.
So, how to solve this problem?

17 Aug 2010 Plot an ellipse in "center form" Draws 2D and 3D ellipses that are given in "center form". Author: Nima Moshtagh Nima Moshtagh

Here is a link to the (unpublished) paper describing the algorithm and math behind the code:

https://sites.google.com/site/nimamoshtagh/software/MVEE.pdf?attredirects=0

17 Jul 2010 Plot an ellipse in "center form" Draws 2D and 3D ellipses that are given in "center form". Author: Nima Moshtagh Bismark Nkansah

Good work, Nima. I've been trying to follow the link to study the mathematical basis for the algoritm, but without success. Could you please help me?
Is it possible that in determining the minimum volume we can assign weights to the points such that the farther away a point is from the main 'cloud' the smaller its weight?
Thanks a lot.

03 Jun 2010 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh Nima Moshtagh

Here is a link to the (unpublished) paper describing the algorithm and math behind the code:

https://sites.google.com/site/nimamoshtagh/software/MVEE.pdf?attredirects=0

05 May 2010 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh Reza Jafari

I would like to thank you the author for the useful code which he developed. It solved many of my problems. The only problem which I faced was due to the singularity of Matrix X in line 76 and singularity of Matrix P * U * P' - (P * u)*(P*u)' in line 96. Do you have any suggestion to avoid singularity for these two matrices?

Appreciated.

Regards,
Reza

26 Jan 2010 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh Rashed

Hi,

I have a problem in 3D. Say, I have an 3D array of P(5,5,5) and how can I make this to work? Please suggest. Or, do I need to produce a matrix P containing the coordinates of the region?

25 Jan 2010 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh Rashed

Thanks a lot. I was looking for something like this.

18 Jun 2009 Plot an ellipse in "center form" Draws 2D and 3D ellipses that are given in "center form". Author: Nima Moshtagh Nima Moshtagh

Here is a paper describing the "minimum volume enclosing ellipse" algorithm and the math behind the code: http://www.seas.upenn.edu/~nima/papers/Mim_vol_ellipse.pdf

18 Jun 2009 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh Nima Moshtagh

Here is a paper describing the algorithm and math behind the code: http://www.seas.upenn.edu/~nima/papers/Mim_vol_ellipse.pdf

15 Feb 2009 Plot an ellipse in "center form" Draws 2D and 3D ellipses that are given in "center form". Author: Nima Moshtagh Tony Mei

Terrific!
Well, good programs! However, Nima, could you please show me some reference link to the mathematical basis of your algorithm ? Thanks a lot.

08 Feb 2009 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh Avinash Uppuluri

Can you also provide a good journal reference for this algorithm. Thanks!

08 Feb 2009 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh Avinash Uppuluri

Hello Nima Moshtagh, The code posted was very useful. Is there a way to add a weight to the points, giving the importance of each point to be included within the ellipse. (Instead of using the tolerance which excludes points through the periphery). With the idea that points that are of less significance need not be included in the ellipse. Where can I include such a weighing parameter. I can probably do it in the pre-processing stage but is there a way to include it within your code. Thanks!

18 Oct 2008 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh

THank you

04 Sep 2008 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh

Very good program. It has helped me a lot to do with the matlab. Thanks to Nima Moshtagh for submitting the code.

04 Sep 2008 Plot an ellipse in "center form" Draws 2D and 3D ellipses that are given in "center form". Author: Nima Moshtagh

Earlier I was doing only maths! But this has given me the joy of visualization.

27 May 2008 Plot an ellipse in "center form" Draws 2D and 3D ellipses that are given in "center form". Author: Nima Moshtagh

Exactly what I was searching for! Thanks!:)

28 Apr 2008 Regular Polygons Plots the regular polygon {N/d} with vertices on a circle of radius 'rad'. Author: Nima Moshtagh

08 Apr 2008 Plot an ellipse in "center form" Draws 2D and 3D ellipses that are given in "center form". Author: Nima Moshtagh

works like a charm

15 Nov 2007 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh

Dear Ondrej Danko,
Thank you for bringing this point to my attention. The outcome that a number of points fall outside of the ellipsoid is expected, because we are truncating the algorithm before reaching its optimal value. The amount of error that we will get by doing this, is of the order of parameter 'tolerance', which represents the amount of error you can tolerate in the final result. For example for t=0.001 the average distance of an outside point is of the order of 10^-3.

15 Nov 2007 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh

"Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space"...

I would expect that resulting ellipsoid COVERS all points, I mean no points are outside of the resulting ellipsoid...

I had ran a small test if it is so... and surprisingly not all points are necessarily inside.

P = rand(3,N);
[A , C] = MinVolEllipse(P, t);
for j = 1:N
if ((P(:,j)-C)'*A*(P(:,j)-C) > 1)
disp('Point is outside...');
end
end

I am missing something, or it is expected? If expected, any suggestions to modify the algorithm to output ellipsoid strictly covering all points?

20 Oct 2007 Plot an ellipse in "center form" Draws 2D and 3D ellipses that are given in "center form". Author: Nima Moshtagh

I found it quite easy to use and read.

22 Mar 2007 Plot an ellipse in "center form" Draws 2D and 3D ellipses that are given in "center form". Author: Nima Moshtagh

Reply to John Huddleston's comment:

Function ellipsoid.m is an standard MATLAB command. It is included in version R13.

18 Mar 2007 Plot an ellipse in "center form" Draws 2D and 3D ellipses that are given in "center form". Author: Nima Moshtagh

The ellipsoid.m function is missing

[X,Y,Z] = ellipsoid(0,0,0,a,b,c,N);

07 Feb 2007 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh

I find that the run time can be radically improved by recognizing that the only points that determine the bounding ellipsoid are on the convex hull, as used by John D'Errico in his minboundsphere. Given points P, the following code finds the reduced set of points lying on the hull.

K=convhulln(P.');
K=unique(K(:));
Q=P(:,K);

for P=randn(3,500)
my computer runs MinVolEllipse(P, .001) in 12.54 seconds

and finds Q followed by MinVolEllipse(Q, .001) in 0.08 seconds

16 Sep 2006 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh

This is a very good program for doing minimum volume ellipsoids. it has been very helpful and the author has as well.

29 Aug 2006 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh

Excellent stuff! This was exactly what I was looking for and works quite well. Although the math behind it all was a bit beyond me, the author was more than helpful in helping me make the most of what the code has to offer, thanks again Nima!

15 Jan 2006 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh

For tolerance=0.01 in 2D here is how long it takes (approximatly) to find the covering ellipse on a 2.4GHz computer:

#point time(sec)
------ --------
100 0.03
500 1.24
1000 5.20
1500 13.26
2000 25.27

09 Jan 2006 Minimum Volume Enclosing Ellipsoid Computes the minimum-volume covering ellipoid that encloses N points in a D-dimensional space. Author: Nima Moshtagh

This could be useful IF you have small sets of data.

I tested this for several problems, in 1, 2 and 5 dimensions. All seemed to work. The only downside is data of even moderate size. The author gives an example with 100 points, solved fairly quickly. But expand that to only 500 points (in 2-d) and it takes 140 seconds to run on my computer.

Contact us