Smallest ellipse by area to enclose 2D points

Question

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 so, 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!

Answer 1

• 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.

Answer 2

See these papers and the references therein:

• B. Gärtner, S. Schönherr, Smallest Enclosing Ellipses - Fast and Exact

• B. Gärtner, S. Schönherr, Smallest Enclosing Ellipses - An Exact and Generic Implementation