Algorithm for Finding all Empty Ellipses Locked by a Set of Points Is there an algorithm for reporting all empty ellipses, that are locked by a finite set $\mathcal{P}$ of points in the euclidean plane?  


*

*An ellipse is considered empty, if no inner point is an element of $\mathcal{P}$.  

*An ellipse is locked by $\mathcal{P}$, if every rotation, translation by an arbitrarily small amount renders the ellipse non-empty; the elements of a continuum of ellipses, which are in contact with the same points are not considered to be locked.  
Any information about the problem of determining the set of all locked empty ellipses for a given set of points $\mathcal{P}$ (e.g. complexity of algorithms, bounds on the number of ellipses, etc.) would be appreciated.
 A: This is not a direct answer, but the techniques in this paper seem applicable to your problem:

Dwyer, Rex A., and William F. Eddy. "Maximal empty ellipsoids." International Journal of Computational Geometry & Applications 6.02 (1996): 169-185.

They enumerate maximal empty ellipsoids, which are defined differently from your
notion of "locked": a maximal empty ellipse is one such that every infinitesimal perturbation of its center, axis lengths,
or orientation yields an ellipse that is either smaller or not empty.

           


So this leads to $\Theta(n^2)$ maximal empty ellipses in $d=2$.

The main technique is to map the problem in $\mathbb{R}^2$ to
enumerating the facets of a convex hull in $\mathbb{R}^5$,
and analogously for arbitrary $d$.
The complexity then follows from the upper-bound theorem for convex polytopes.

     


A: The location of an ellipse center, and its size and shape are given by 4 real parameters. Throw in rotation with respect to a fixed coordinate system, and you have five-ish real parameters to play with. This suggests to me that you will need to look at subsets of five points of P to determine what is locked.
Motivated by my square example in the comments, I would consider developing an algorithm that, given four points, determines the envelope of the continuum of ellipses going through those four points.  Once you have such an envelope, determine which points of P lie inside the envelope, and use that to determine which ellipses are locked. Note that you avoid processing points outside the envelope.
You might be clever on how to develop an envelope using just three points, giving you smarter choices for the fourth and fifth points, but I don't know if smarter means faster.
Gerhard "Maybe Grobner Bases Would Help?" Paseman, 2016.10.12.
