非相交椭圆的最近三个邻居

Question

我正在解决一个问题，即找到一组任意放置的不相交椭圆中最接近的三个邻居。作为新用户，我不允许包含图像标签，但我在页面底部包含了URL，因为我总是认为通过视觉辅助工具更能清楚地解释自己的意思。图片展示了阿波罗尼斯圆连接三个最近的椭圆之间的情况。

到目前为止，我已经尝试使用椭圆之间的最小距离，并通过增量和扫描线方法修改德劳内三角剖分，使用涉及每个三个椭圆配置形成的三角形的内切圆等各种技术来尝试估计邻居，并尝试使用边界框来解决问题，但已经完全没有想法如何使其高效工作。

虽然我已经找到了解决方案，但它需要穷举比较每个三元组与其他椭圆的距离，并且时间复杂度为n(n-1)(n-2)/3!。此外，每次计算都是迭代而非代数计算。

是否有人有关于如何以低于n^2的时间复杂度代数地解决这个问题的想法？

即使是一点点技巧的建议，我也愿意尝试一下，因为现在我已经在这个问题上工作了将近3周，但仍然离一个合理的答案很远。

- Ross Walker

---

我在MathOverflow上回答了这个问题链接。正如@zamazalotta所说，但还有更多要说的。 - Joseph O'Rourke

Answer 1

如果您为椭圆计算了 Voronoi 图，则您的圆心将被放置在这些图的交点处。

参考链接：http://ima.umn.edu/nuggets/voronoi.html

- zamazalotta

---

谢谢，我现在要尝试 Voronoi 图方法。 - Ross Walker

Answer 2

你可以根据椭圆的边界框将它们打包进一个基于R-tree的数据结构中。 R-tree是一种用于空间对象的类似二叉树的数据结构，并支持通过遍历进行有效的最近邻和第k个最近邻查询。

对于具有许多椭圆的大型数据集，使用R树应显着减少距离测试的数量，仅扫描查询附近的子树的子集。

希望这可以帮助您。

- Darren Engwirda

---

Darren，感谢您的建议，我想我会尝试重新计算Voronoi图，就像@Joseph O'Rourke（Math Overflow）建议的那样，因为找到与三元组相关联的顶点是我的下一步，所以我将同时得到答案。虽然如果我无法使其正常工作，就像在发布论坛帖子之前尝试过的那样，我肯定会尝试您的建议，因为在看了它之后，由于减少了距离搜索的数量，我非常喜欢它的声音；搜索速度对我的工作至关重要。再次感谢您的帮助。罗斯。 - Ross Walker