algorithm - 不相交椭圆的最近邻居三重奏

Question

我正在研究一个问题，即为一组任意放置的不相交椭圆找到最近的三个邻居。作为新用户，我不允许包含图像标签，但我在页面底部包含了 URL，因为我一直认为我能够更好地用视觉辅助工具来解释自己。该图展示了我所说的 Apollo 尼乌斯圆将 3 个最近的椭圆相互连接起来的意思。

到目前为止，我已经尝试使用椭圆之间的最小距离并通过增量和扫描线方法修改 Delaunay 三角剖分，使用各种技术涉及在每 3 个椭圆配置之间形成的三角形圆圈等，并尝试估计具有边界的邻居盒子，并且完全没有关于如何真正有效地工作的想法

虽然我已经找到了一个解决方案，但它涉及详尽地搜索每个三个椭圆并将其与其他每个椭圆进行比较，并且时间复杂度为 n(n-1)(n-2)/3!。最重要的是，每个计算都是迭代完成的，而不是代数计算的。

有没有人知道如何用代数的方式来解决这个问题，而且时间复杂度低于 n^2？

即使是一种技术建议也适合我尝试，因为现在我已经研究了将近 3 周，但确实离一个不错的答案还差得很远。

Answer 1

如果您为椭圆计算 Voronoi 图，那么您的圆心点将位于图的交点处。

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