5
$\begingroup$

I am interested in writing an algorithm that, for a given set of $n$ points in $\mathbb{R}^2$, finds the equation of the smallest ellipse by area to enclose all $n$ points. Here's where I'm at:

The general equation of an ellipse is $Ax^2+Bxy+Cy^2+Dx+Ey-1=0$. This ellipse has area $\frac{2\pi}{\sqrt{4AC-B^2}}$ and by definition satisfies $4AC-B^2>0$. Therefore to minimize the area of this conic, we can minimize the scalar value function $\phi(x)=B^2-4AC$.

I'm going to simplify this question to emphasize the part I don't understand. Imagine now that we have only 3 points that need to be enclosed in the ellipse, (1,1), (1,5), and (7,3). Because there are only 3 points, we can assume the smallest ellipse would pass through all 3, and we now have a quadratic optimization problem under equality constraints as follows:

$$\min_{x}\phi(x)=B^2-4AC$$

s.t.

$$c_{1}(x) = A+B+C+D+E-1=0$$ $$c_{2}(x)=A+5B+25C+D+5E-1=0$$ $$c_{3}(x)=49A+21B+9C+7D+3E-1=0$$

where $x = $ $[A$ $B$ $C$ $D$ $E]^{T}$

Using Lagrange multipliers, we have Lagrangian

$$\mathcal{L}(x,\lambda) = \phi(x)-\lambda_{1}c_{1}(x)-\lambda_{2}c_{2}(x)-\lambda_{3}c_{3}(x)$$

We now set $\nabla_{x}\mathcal{L} = 0$ and $\nabla_{\lambda}\mathcal{L} = 0$. These conditions (KKT) produce an 8 x 8 linear system. Tediously, here it is:

$$\begin{bmatrix} 0 &0 &4 &0 &0 &1 &1 &49 \\ 0 &-2 &0 & 0 &0 &1 &5 &21\\ 4 &0 &0 &0 &0 &1 &25 &9\\ 0 &0 &0&0&0&1&1&7\\ 0 &0&0&0&0&1&5&3\\ 1&1&1&1&1&0&0&0\\ 1&5&25&1&5&0&0&0\\ 49&21&9&7&3&0&0&0\\ \end{bmatrix} \begin{bmatrix} A\\ B\\ C\\ D\\ E\\ \lambda_{1}\\ \lambda_{2}\\ \lambda_{3}\\ \end{bmatrix} = \begin{bmatrix} 0\\0\\0\\0\\0\\1\\1\\1\\ \end{bmatrix}$$

This is the equivalent of the saddle point matrix, and is nonsingular. I think this makes sense because reasonably there should only be one smallest ellipse that encloses the 3 given points.

The issue is that the solution to this linear system produces a Langrange multiplier that is negative, and the entire solution when plotted is obviously wrong. So here are my questions:

1) Am I setting this problem up correctly?

2) If 1) = yes, what is an intuitive explanation as to why this method is not producing a feasible solution.

3) What method would you recommend, considering that this is a simplified version of the problem? The ultimate goal will be to find the ellipse that will enclose $n$ points, which will produce a quadratic optimization problem under inequality constraints.

Any help is appreciated! Thanks a lot guys.

$\endgroup$
  • 2
    $\begingroup$ $\dfrac{2\pi}{\sqrt{4AC-B^2}}$ is the area for central ellipse $Ax^2+Bxy+Cy^2=1$ only. Minimizing ellipse implies maximizing $4AC-B^2$. Note that for a triangle inscribed in a given ellipse, the maximal triangle with the eccentric angles for the vertices differ by $120^{\circ}$. $\endgroup$ – Ng Chung Tak Oct 21 '18 at 19:44
  • $\begingroup$ @NgChungTak, I believe this formula holds for a translated ellipse as well since by definition a translation preserves all properties of a shape and is only a transformation on its location. That is an interesting note about the inscribed triangle. Do you see a way that could be applied in this problem? $\endgroup$ – Cooper Maira Oct 21 '18 at 21:09
  • $\begingroup$ Translation normally doesn’t affect the quadratic part of the general conic equation, but it does affect the constant term. In the equation you’re using, this term is normalized to $-1$. Doing so involves scaling the quadratic part of the equation, so a translation also effectively changes the scale. $\endgroup$ – amd Oct 21 '18 at 23:15
  • $\begingroup$ See also cs.cornell.edu/cv/OtherPdf/Ellipse.pdf $\endgroup$ – lhf Oct 22 '18 at 11:41
1
$\begingroup$

See these papers and the references therein:

$\endgroup$
1
$\begingroup$
  • Area of a triangle with vertices at eccentric angles $\alpha$, $\beta$ and $\gamma$ is

    $$\Delta=2ab \left | \sin \frac{\alpha-\beta}{2} \sin \frac{\beta-\gamma}{2} \sin \frac{\gamma-\alpha}{2} \right |$$

  • The triangle's area is maximal when $\alpha-\beta=\beta-\gamma=\pm 120^{\circ}$, that is

    $$\Delta=\frac{3\sqrt{3}}{4}ab$$

  • Note that

    $$\sin x+\sin (x+120^{\circ})+\sin (x+240^{\circ})=0$$

    $$\cos x+\cos (x+120^{\circ})+\cos (x+240^{\circ})=0$$

    the centroid $G$ for maximal triangle is an invariant that is the centre of the ellipse.

  • Let $\boldsymbol{u}=\vec{GA}$, $\boldsymbol{v}=\vec{GB}$, $\boldsymbol{w}=\vec{GC}$, the column vectors for the semi-axes be $\boldsymbol{\lambda}$ and $\boldsymbol{\mu}$.

    Now

    \begin{align} \boldsymbol{0} &= \boldsymbol{u}+\boldsymbol{v}+\boldsymbol{w} \\[5pt] \boldsymbol{u} &= \boldsymbol{\lambda} \cos (\theta-60^{\circ})+ \boldsymbol{\mu} \sin (\theta-60^{\circ}) \\[5pt] \boldsymbol{v} &= \boldsymbol{\lambda} \cos (\theta+60^{\circ})+ \boldsymbol{\mu} \sin (\theta+60^{\circ}) \\[5pt] \boldsymbol{\lambda} &= \frac{2[\boldsymbol{u}\sin (\theta+60^{\circ})- \boldsymbol{v}\sin (\theta-60^{\circ})]}{\sqrt{3}} \\[5pt] \boldsymbol{\mu} &= \frac{2[\boldsymbol{v}\cos (\theta-60^{\circ})- \boldsymbol{u}\cos (\theta+60^{\circ})]}{\sqrt{3}} \\[5pt] 0 &= \boldsymbol{\lambda} \cdot \boldsymbol{\mu} \\[5pt] 0 &= \boldsymbol{u} \cdot \boldsymbol{v} \sin 2\theta- \frac{u^2}{2} \sin (2\theta+120^{\circ})- \frac{v^2}{2} \sin (2\theta-120^{\circ}) \\[5pt] \tan 2\theta &= \frac{u^2-v^2}{u^2+4\boldsymbol{u} \cdot \boldsymbol{v}+v^2} \sqrt{3} \end{align}

  • Also note that

    \begin{align} \boldsymbol{u} \times \boldsymbol{v} &= \frac{\sqrt{3}}{2} \boldsymbol{\lambda} \times \boldsymbol{\mu} \\[5pt] |\boldsymbol{u} \times \boldsymbol{v}| &= \dfrac{2\Delta}{3} \\[5pt] A_{\text{min}} &= \pi \lambda \mu \\[5pt] &= \frac{2\pi}{\sqrt{3}} |\boldsymbol{u} \times \boldsymbol{v}| \\[5pt] &= \dfrac{4\pi \Delta}{3\sqrt{3}} \\[5pt] \end{align}

  • The (column) vector equation for the central conics is given by

    $$\boldsymbol{x}^T \mathbb{M} \, \boldsymbol{x}=1$$

    $$\mathbb{M}^{-1}= \begin{pmatrix} \boldsymbol{\lambda} & \boldsymbol{\mu} \end{pmatrix} \begin{pmatrix} \boldsymbol{\lambda}^T \\ \boldsymbol{\mu}^T \end{pmatrix}$$

Updates

The smallest ellipse is also known as Steiner circumellipse.

The Steiner inellipse has the maximum area of any inellipse.

The Steiner inellipse is half of the Steiner circumellipse about the centroid of the triangle.

If $\alpha$, $\beta$, $\gamma \in \mathbb{C}$ are the vertices of the triangle and let

$$f(z)=(z-\alpha)(z-\beta)(z-\gamma)$$

then by Marden's_theorem the foci of the Steiner inellipse is given by

$$ f'(c)=0 \implies c=\frac{\alpha+\beta+\gamma}{3} \pm \frac{\sqrt{\alpha^2+\beta^2+\gamma^2- \beta \gamma-\gamma \alpha-\alpha \beta}}{3}$$

Doubling the focal length immediately gives the foci for the Steiner circumellipse which are

$$\frac{\alpha+\beta+\gamma}{3} \pm \frac{2\sqrt{\alpha^2+\beta^2+\gamma^2- \beta \gamma-\gamma \alpha-\alpha \beta}}{3}$$

See also an article here for your further interest.

$\endgroup$
  • $\begingroup$ Under your forth bullet you start using theta. Could you clarify what theta is? $\endgroup$ – Cooper Maira Oct 24 '18 at 21:26
  • $\begingroup$ Could you also clarify what the vector x is (used under your last bullet point), and what the scalar values u, v, mu, and lambda are? Are these scalars meant to be the magnitude of their respective vectors? $\endgroup$ – Cooper Maira Oct 24 '18 at 21:45
  • $\begingroup$ $\theta-60^{\circ}$, $\theta+60^{\circ}$ and $\theta+180^{\circ}$ are eccentric angles where $$\theta=\frac{1}{2} \tan^{-1} \frac{(u^2-v^2)\sqrt{3}}{u^2-\boldsymbol{u} \cdot \boldsymbol{v}+v^2}$$ $\endgroup$ – Ng Chung Tak Oct 25 '18 at 11:45
  • $\begingroup$ All the bold italic are colume vectors $$\boldsymbol{x}=\begin{pmatrix} x \\ y \\ 0 \end{pmatrix}$$ $$\boldsymbol{u}=\vec{GA}=\begin{pmatrix} x_1-\dfrac{x_1+x_2+x_3}{3} \\ y_1-\dfrac{y_1+y_2+y_3}{3} \\ 0 \end{pmatrix}$$ and so on $\endgroup$ – Ng Chung Tak Oct 25 '18 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.