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

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?

share|improve this question
    
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
1  
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
1  
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
1  
@Will: Thank you, Will. That is very clever! –  Joseph O'Rourke Feb 6 '13 at 13:13
show 2 more comments

2 Answers

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.

share|improve this answer
add comment

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:
           TwoEllipses1
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:
           TwoEllipses2
Compute the major axis of the transformed $E_2$:
           TwoEllipses3
Rotate $E_2$ down so its major axis is along the $x$-axes:
           TwoEllipses4
Now it is clear what the minimum area enclosing ellipse is, as its two axes are determined by the ellipse and the circle:
           TwoEllipses5
Rotate back, and unscale:
           TwoEllipses6


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

share|improve this answer
    
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
1  
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
add comment

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.