3
$\begingroup$

I'm working on a problem which is to find the closest trio of neighbours for a set of arbitrarily placed non-intersecting ellipses. As a new user I'm not allowed to include image tags but I've included the URL at the bottom of the page as I always think I'm better able to explain myself with visual aids. The picture demonstrates what I mean with Apollonius circles connecting the 3 nearest ellipses to one another.

enter image description here

So far I have tried using the minimum distances between the ellipses and modifying Delaunay Triangulation, via incremental and sweepline methods, used various techniques involving in circles of triangles formed between every 3 ellipse configuration etc, and attempted to estimate the neighbours with bounding boxes, and have completely run out of ideas of how to actually get this working efficiently

Although I have worked out a solution it involves exhaustively searching and comparing every trio of ellipses with every other ellipse and has a time complexity of n(n-1)(n-2)/3!. And on top of that each calculation is done iteratively rather than algebraically.

Would anyone even have an idea of how to go about this that could be done algebraically and at lower then a n^2 time complexity?

Even a suggestion of a technique would suit me to have a try at, because right now I've been working at it for nearly 3 weeks and really am no closer to a decent answer.

Thank you in advance for any help,

Ross.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

Essentially you want to compute the Voronoi diagram of the ellipses. Then the solution you seek is provided by a circle centered on some vertex of the diagram. The work by Karavelas and Yvinec seems the most advanced on this problem, considering more general convex objects, permitted to intersect. They detail an incremental algorithm (add one object at a time to a growing diagram) that requires only $O(\log^2 n)$ time per insertion in your circumstance, and so leads to $O(n \log^2 n)$ time overlall, for $n$ ellipses.

Here is a nice figure from their paper:
      Yvinec
Condensed: "The Voronoi diagram of planar convex objects," European Symp.on Algorithms, 2003. Full: "The Voronoi Diagram of Convex Objects in the Plane" (PDF link).

Although implementation of the Karavelas and Yvinec algorithm is not straightforward, it has been accomplished, in CGAL: "A CGAL-based implementation for the Voronoi diagram of ellipses" by Emiris, Hemmer, Tsigaridas, and Tzoumas, 2008 (PDF link):
           VorDiag

Improve this answer
$\endgroup$
4
  • $\begingroup$ Joseph, Thank you for that, I looked at the VD of ellipses in GCAL before I started, but to be fair the reason I didn't use that approach is becuase I can't understand ANY of the code used in the GCAL algorithm; probably because I have no knowledge of C++. So I was trying to find a differnt way that didn't involve VDs, although as you said it is the way to find the answer, plus finding the vertex point of the 'ellipse trio' would be my next stage, so this would be 2 birds with one stone. I will go back to it as you suggest & try to understand what it's talking about, thank you again. Ross. $\endgroup$
    – Ross
    Commented Feb 28, 2012 at 17:25
  • $\begingroup$ Understanding CGAL code is a significant challenge. It is not just C++; all the CGAL data types and patterns and library functions need be mastered. $\endgroup$
    – Joseph O'Rourke
    Commented Feb 28, 2012 at 17:38
  • $\begingroup$ Well I love a challenge, hopefully it will come to me in time. Alas a mere copy and past of the code never seems to work, even the working examples that are given come littered with red squiggles when I open them with MS Visual and always fail when compiled; but I suppose not everything can have a quick fix. $\endgroup$
    – Ross
    Commented Feb 28, 2012 at 17:44
  • $\begingroup$ See also my reply to a related question at MSE. The algebraic degree of the computations can be quite large. $\endgroup$
    – Joseph O'Rourke
    Commented Sep 3, 2017 at 13:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .