# Maximum area ellipse that does not include a set of points

I'm interested in finding the maximum area ellipse that does not cover some points $\mathbf{p}_i$ and that is centered at the origin. Hence, ideally I'd like to solve this optimization problem: $$\begin{array}{rl} \operatorname{maximize} & \det \boldsymbol \Sigma \\ \operatorname{subject to} & \boldsymbol \Sigma \succeq \mathbf{0} \\ & \mathbf{p}_i^T \boldsymbol \Sigma^{-1} \mathbf{p}_i \ge 1 \quad \forall i \end{array}$$ The ellipse would be thus defined by the equation $\mathbf{p}_i^T \boldsymbol \Sigma^{-1} \mathbf{p}_i = 1$. Is there a known/reliable method to solve such a problem (with many $\mathbf{p}_i$)?

What I've tried: Substituting $\boldsymbol \Omega=\boldsymbol \Sigma^{-1}$ doesn't help: $$\begin{array}{rl} \operatorname{minimize} & \det \boldsymbol \Omega \\ \operatorname{subject to} & \boldsymbol \Omega \succeq \mathbf{0} \\ & \mathbf{p}_i^T \boldsymbol \Omega\,\mathbf{p}_i \ge 1 \quad \forall i \end{array}$$ The constraints are nice and convex (linear matrix inequality and a set of scalar linear inequalities), the problem is the objective function which is concave, hence no go.

You can give a sort of estimate to the solution by replacing the objective with $\operatorname{tr}\boldsymbol\Omega$; this would make the objective linear and would also be equivalent (at least in the 2D case) to maximizing $\displaystyle\frac{\det\boldsymbol\Sigma}{\operatorname{tr}\boldsymbol\Sigma}$, which is kind of similar, but not really the same.

Also, my gut tells me that the optimal ellipse should cross three of the $\mathbf{p}_i$ points. This implies that you could find the optimum by enumerating all sets of three points, fitting an ellipse through them (if possible), checking if all other points fall outside, and keeping the ellipse with the largest area. For pathological cases you could then also check all combinations of two points by fitting the maximum area ellipse passing through them...

The problem with this approach is that: (a) I don't know if it is in fact optimal, it's merely a gut feeling (b) I don't like it, it's sort of brute force and it has $\Theta(n^4)$ time complexity.

Any suggestions?

EDIT: As MvG pointed out, the solution to the problem is unbounded. So let us consider the additional constraint $\boldsymbol\Sigma\preceq\sigma\mathbf{I}$ (equivalently $\boldsymbol\Omega\succeq\frac{\mathbf{I}}{\sigma}$)

## 1 Answer

I'd argue that for a finite number of points to avoid, the possible area is in fact unbounded. You will always be able to find a strip of finite width but infinite length, bounded by two parallel lines and symmetric with respect to the origin, in which you can place ellipses of arbitrary area. • @LucasVB: True, but that would be a different question. You might also limit the aspect ratio of the ellipse in some arbitrary way, or stuff like that. – MvG Jul 31 '14 at 20:39
• Sorry, I deleted the comment since I realized it wouldn't be a really great condition to begin with. (What I suggested was using the convex hull defined by the points. But if we have 4 points in a square, the maximum ellipse, a circle, would poke out between two vertices. It isn't a natural as a condition as I initially though. It works, but yeah, MvG's excellent point needs to be addressed.) – LucasVB Jul 31 '14 at 20:41
• Hmmm, you are right. But I admit I'm not really interested in an unbounded solution, so let me change the problem a bit, let's assume you have a bound on the maximum axis length, i.e. a constraint of the form $\boldsymbol\Sigma \preceq \sigma \mathbf{I}$ how would that change matters? – horqat Jul 31 '14 at 20:43