2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ If P are the vertices of a square, what do you want to do, list the continuum many ellipses that are locked? Gerhard "A Really Bad Edge Case" Paseman, 2016.10.11. $\endgroup$
    – Gerhard Paseman
    Oct 12, 2016 at 5:43
  • $\begingroup$ @GerhardPaseman in my question I clarified that an ellipse is locked (among other criteria) if neither of the major axis can be elongated while remaining empty, so in the case of the vertices of a square, the set of locked ellipses is empty; the emphasis is on empty and locked. $\endgroup$
    – Manfred Weis
    Oct 12, 2016 at 5:56
  • $\begingroup$ @GerhardPaseman but I see, that I have to edit the question to address your critique. $\endgroup$
    – Manfred Weis
    Oct 12, 2016 at 6:02

2 Answers 2

Reset to default
2
$\begingroup$

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.

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

      MaxEllipse1

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thanks Joseph! That definition of maximal empty ellipses matches exactly what I meant by "locked"; as you can see in my question, I had ruled out "continuums" of empty ellipses (in response to Gerhard's critque). $\endgroup$
    – Manfred Weis
    Oct 13, 2016 at 0:33
  • $\begingroup$ Incidentally, the reason that $\mathbb{R}^5$ plays a role is essentially @GerhardPaseman's $5$ parameters $\endgroup$
    – Joseph O'Rourke
    Oct 13, 2016 at 11:29
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ A good preprocessing step is to list (or generate on the fly) all triples of points of P which have no point of P on the triangle formed by such a triple. This should be a simple computation that allows you to pick good sets of four points and avoid bad sets of four and five points. This alone should turn your algorithm into a hopefully cubic-time algorithm in the number of points. Gerhard "Likes Nice And Easy Approximations" Paseman, 2016.10.12. $\endgroup$
    – Gerhard Paseman
    Oct 12, 2016 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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