我知道 MST 是 delauny 三角剖分的一个子集，但它如何帮助找到最小生成树？当我对 MST 使用 delauny 三角剖分的边缘时，这意味着什么？这与在找到 MST 之前不对一组点进行三角测量有何不同？
问问题
657 次
1 回答
2
标准的 mst 算法在图上运行。如果您从一组顶点开始，除了顶点之间的成对（抽象）距离之外没有任何其他信息，那么您的标准方法将要求您在带有O(n^2)边的完整图上运行 mst 算法。由于标准 mst 算法的复杂性取决于边的数量（例如，O(e log e)对于 Kruskal），因此如果您可以减少图形中的边数开始时会更有效 - 这适用于被视为的 delaunay 三角剖分图，因为它运动O(n)边缘（我不会讨论原始点集的 mst 是 delaunay 图的子集，正如您所承认的那样）。
您的原始点集可能会受到其他约束，这些约束要么阻止 delaunay 三角剖分（例如共线点），要么允许从更稀疏的图形开始（例如，最小直径小于两点之间最小距离的凸包在你的点集中）。
问候，卡斯滕
于 2012-02-28T17:42:00.237 回答