# Find minimum-area ellipse which encloses two ellipses

I need an efficient algorithm to find the ellipse with the smallest possible area which encloses two given ellipses. The given ellipses are constrained to have coincident centers at the origin but can have any orientation. The problem is limited to two dimensions. Any ideas?

-
See the previous MO question, "Enlcosing a set of ellipses within one ellipse," mathoverflow.net/questions/119663 , where I cite a paper that might help you. –  Joseph O'Rourke Feb 6 '13 at 2:02
This sounds like homework....??? –  Suvrit Feb 6 '13 at 2:02
I looked at the paper. Given the specialization of my problem I was hoping for a simpler solution. This isn't homework although I am thinking about at home and at work. It happens to be a problem I am trying to solve for the work I do. Not that I see the relevance of the question. –  Dave Feb 6 '13 at 2:12
You could sprinkle some points on the ellipses and then use this algorithm: "Smallest Enclosing Ellipses--An Exact and Generic Implementation in C++" inf.fu-berlin.de/inst/pubs/tr-b-98-05.abstract.html But given your special circumstances it likely does have an efficient, exact solution. –  Joseph O'Rourke Feb 6 '13 at 2:16
@Will: Thank you, Will. That is very clever! –  Joseph O'Rourke Feb 6 '13 at 13:13

Yeah, there is a shear transformation that takes one of the ellipses to a circle. The least area ellipse enclosing the resulting figure is now evident by symmetry. Then use the inverse of the shear.

Now that I think of it, you can just shrink along the major axis of one of the ellipses and expand on the minor axis to get the circle.

All manipulations involved are with 2 by 2 matrices. The hypothesis of coincident centers is crucial.

-

Below is an example to illustrate Will Jagy's solution. (Caveat lector: I did not preserve scale from image to image.) First, it is no loss of generality to rotate so that one ellipse $E_1$ has its major axis along the $x$-axis:

Now transform by scaling the long axis down and the short axis up so that $E_1$ becomes a circle. The determinant of this transformation matrix is $1$, so areas are preserved. The second ellipse $E_2$ is transformed to another ellipse:

Compute the major axis of the transformed $E_2$:

Rotate $E_2$ down so its major axis is along the $x$-axes:

Now it is clear what the minimum area enclosing ellipse is, as its two axes are determined by the ellipse and the circle:

Rotate back, and unscale:

Here is Will Jagy's drawing as he mentions in his comment below:

-
Very good. I sent you an email with an example jpeg, showing that iterating this process for many concentric ellipses need not give the enclosing ellipse of least area. Iterating the process is what the OP intends, and it won't so so poorly either. –  Will Jagy Feb 8 '13 at 20:18
Thanks, Joseph. For those keeping score at home, the first two ellipses are the narrow black ones, and the enclosing ellipse is the first orange-red circle. If I now add in a third ellipse, blue, the process gives the larger orange-red ellipse as the enclosure. However, this is not the least possible area anymore. The least-area enclosing ellipse is a bit narrower and, in particular, is tangent to all three original ellipses, two black and one blue. –  Will Jagy Feb 8 '13 at 21:11