Nearest trio of neighbors for disjoint ellipses

Question

I am working on a problem, which is to find the nearest three neighbors for a set of randomly located disjoint ellipses. As a new user, I am not allowed to include image tags, but I have included the URL at the bottom of the page, as I always think I will better explain myself with visual aids. The figure shows what I mean by Apollonius circles connecting the 3 nearest ellipses to each other.

So far, I have tried to use the minimum distance between ellipses and modify the Delaunay triangulation using incremental methods and pivot lines, I used various methods, including triangle circles formed between every 3 ellipse configurations, etc., and tried to evaluate the neighbors using bounding rectangle boxes , and completely exhausted ideas on how to actually make it work effectively

Although I developed the solution, it includes an exhaustive search and comparison of each trio of ellipses with each other ellipse and has a time complexity of n(n-1)(n-2)/3! . And on top of that, every calculation is performed iteratively, not algebraically.

Can anyone have an idea of ​​how to do this, which can be done algebraically and with less time complexity n^2 ?

Even the technology proposal is suitable for me to try, because now I have been working on it for almost 3 weeks and actually not closer to a decent answer.

Answer 1

If you calculate the Voronoi diagram for your ellipses, then the center points of your circles will be placed at the intersection of the diagrams.

http://ima.umn.edu/nuggets/voronoi.html

Answer 2

You can pack your ellipses in an R-tree based on their bounding fields. The R-tree is a binary-tree data structure for features and supports efficient near and near queries of the nearest neighbor and kth using traversal.

For large datasets with many ellipses, using the R-tree should significantly reduce the number of distance tests, only scanning a subset of the tree in the vicinity of the query.

Hope this helps.