欧氏最小生成树与Delaunay三角剖分

Question

我想根据二维平面上一组点之间的欧几里德距离来计算最小生成树。我当前的代码存储所有的边，然后执行Prim算法以得到最小生成树。但是，我知道这样做会占用所有边的O(n^2)空间。在

通过研究发现，如果先在这组点上计算delaunay三角剖分，然后在三角剖分的边上运行Prim或Kruskal算法得到最小生成树，内存和运行时间都可以得到优化。在

这是编程竞赛（https://prologin.org/train/2017/qualification/taxi_des_neiges）的一部分，所以我怀疑我是否能够使用凌乱的空间. 有没有其他方法可以简单地得到Delaunay三角剖分中包含的边？在

提前谢谢。在

Answer 1

看起来Scipy用的是QHull，这。。在这个文件夹的某个地方。。。有执行delaunay三角剖分和获取边的代码（尽管是用C实现的）

https://github.com/scipy/scipy/tree/master/scipy/spatial/qhull/src

Answer 2

模块有帮助吗？以下是一些可能有用的方法：

• ^{}
• ^{}
• ^{}
• ^{}?

你自己滚？这两个都描述了增量算法，Wikipedia似乎是O（n logn）：

• http://www.geom.uiuc.edu/~samuelp/del_project.html
• http://graphics.stanford.edu/courses/cs368-06-spring/handouts/Delaunay_1.pdf

这里的an ActiveState recipe可能有助于开始，但看起来还没有完成。在