Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello,

Is there an algorithm that takes in a set of ellipses and gives back and ellipse that encloses the set?

share|improve this question
    
If you just want an ellipse that encloses the given ones, then a giant circle centered at the origin will do. But you might have meant to enclose the given ones without a lot of extra space. –  Andreas Blass Jan 23 '13 at 15:49
    
yes, this is what i meant. –  lts Jan 23 '13 at 16:53
    
I'm sure there's such an algorithm, and you could try to write one. It shouldn't be too difficult if you define your ellipses as quadratic equations in affine coordinates. Yet I do believe your question is innapropriate for this forum, so you won't receive any other answer. Please read the FAQ. –  Loïc Teyssier Jan 23 '13 at 17:55

2 Answers 2

I don't think the problem of finding a minimum area ellipse enclosing other ellipses (one interpretation of the question) is as straightforward as it might appear. I believe it can be solved in polynomial time via convex optimization, but that might be a heavy hammer, depending on resource constraints. A good hook into the literature on the topic can be found in this paper:

S. Jambawalikar and P. Kumar. "A note on Approximate Minimum Volume Enclosing Ellipsoid of Ellipsoids." 2008. Computational Sciences and Its Applications. (PDF download; IEEE link)


           MinEllipseEllipses

share|improve this answer
2  
Inspired by Joseph's picture, I would suggest the following approach: Build a convex hull approximation of the union of ellipses, then apply a scale transformation to the hull to make it circular roughly, find the smallest enclosing circle, then invert the transformation. Gerhard "Often Inspired By Joseph's Pictures" Paseman, 2013.01.23 –  Gerhard Paseman Jan 23 '13 at 21:48
    
Nothing in the OP question pointed towards a minimizing area ellipse. I maintain it is easy to find a simple algorithm fulfiling the OP question, even with some optimization regarding the size of the enclosing ellipse. Anyway... –  Loïc Teyssier Jan 24 '13 at 7:17

Here is a link to semidefinite programming code for solving this type of problem (for ellipsoids):

CVX based solution of Min volume covering elllipsoids

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.