# Enlcosing a set of ellipses within one ellipse

Hello,

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

-
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

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)

-
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

-