不相交椭圆的最近邻域三元组
不相交椭圆的最近邻域三元组
提问于 2012-02-28 00:21:48
我正在解决一个问题，那就是为一组任意放置的不相交的椭圆找到最近的三个邻居。作为一个新用户，我不允许包含图片标签，但我已经在页面底部添加了URL，因为我总是认为我能够更好地使用视觉辅助工具来解释自己。这张图片展示了我所说的阿波罗尼乌斯圆将3个最近的椭圆彼此连接起来的意思。
到目前为止，我已经尝试使用椭圆之间的最小距离和修改Delaunay三角剖分，通过增量和快线方法，使用各种技术，涉及到每3个椭圆配置之间形成的三角形的圆等，并尝试估计具有边界框的邻居，并且完全没有如何实际有效地进行此工作的想法
尽管我已经想出了一个解决方案，但它涉及到对每三个椭圆进行详尽的搜索和比较，并且具有n(n-1)(n-2)/3!的时间复杂度。最重要的是，每个计算都是迭代进行的，而不是代数计算。
有没有人知道如何在比n^2时间复杂度更低的情况下，以代数的方式完成这项工作？
即使是一个技术建议也适合我试一试，因为现在我已经研究了将近3个星期，真的没有接近一个像样的答案。
回答 2
Stack Overflow用户
发布于 2012-02-28 00:33:38
如果计算椭圆的Voronoi图，则圆的中心点将放置在图的交点处。
http://ima.umn.edu/nuggets/voronoi.html
Stack Overflow用户
发布于 2012-02-28 03:34:55
您可以根据椭圆的边界框将椭圆打包到R-tree中。R-tree是一种类似二叉树的空间对象数据结构，通过遍历来支持高效的最近邻查询和第k个最近邻查询。
对于具有许多椭圆的大型数据集，使用R-树应该可以显著减少距离测试的数量，只扫描查询附近的树的子集。
希望这能有所帮助。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/9468390
复制相关文章
相似问题
腾讯云开发者
