6
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Joseph O'Rourke
    Commented Feb 6, 2013 at 2:02
  • 1
    $\begingroup$ This sounds like homework....??? $\endgroup$
    – Suvrit
    Commented Feb 6, 2013 at 2:02
  • $\begingroup$ 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. $\endgroup$
    – Dave
    Commented Feb 6, 2013 at 2:12
  • 2
    $\begingroup$ 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. $\endgroup$
    – Joseph O'Rourke
    Commented Feb 6, 2013 at 2:16
  • 1
    $\begingroup$ @Will: Thank you, Will. That is very clever! $\endgroup$
    – Joseph O'Rourke
    Commented Feb 6, 2013 at 13:13

2 Answers 2

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
0
7
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Will Jagy
    Commented Feb 8, 2013 at 20:18
  • 1
    $\begingroup$ 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. $\endgroup$
    – Will Jagy
    Commented Feb 8, 2013 at 21:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .