Welcome to MathOverflow

Question

1

Hello,

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

flag	asked Jan 23 at 14:59 lts 11●1

	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 at 15:49
	yes, this is what i meant. – lts Jan 23 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 at 17:55

Joseph O'Rourke · Answer 1 · 2013-01-23 21:35:14Z UTC

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

S. Sra · Answer 2 · 2013-02-06 02:03:54Z UTC

1

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

CVX based solution of Min volume covering elllipsoids

answered Feb 6 at 2:03

S. Sra
10k●1●16●44

Enlcosing a set of ellipses within one ellipse

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.