MST がドローニー三角形分割のサブセットであることは理解していますが、最小スパニング ツリーを見つけるのにどのように役立つのでしょうか? MST にドローニー三角形分割のエッジを使用すると、どのような意味がありますか? これは、MST を見つける前に一連のポイントを三角測量しないこととどう違うのですか?
1 に答える
2
標準の mst アルゴリズムはグラフで動作します。頂点間のペアごとの (抽象的な) 距離以外の情報を持たない頂点のセットから開始する場合、標準的なアプローチでは、O(n^2)エッジを含む完全なグラフに対して mst アルゴリズムを実行する必要があります。標準の mst アルゴリズムの複雑さはエッジの数に依存するO(e log e)ため (例: Kruskal の場合)、開始するグラフのエッジの数を減らすことができればより効率的です。それはエッジをスポーツO(n)するので、グラフです（あなたが認めているように、ドロネーグラフのサブセットである元のポイントセットのmstがあることについては議論しません）。
元の点セットは、ドロネー三角形分割 (例: 共線点) を防止するか、さらにまばらなグラフを開始できるようにする (例: 最小直径が 2 点間の最小距離よりも小さい凸包) の対象となる可能性があります。あなたのポイントセットで）。
よろしく、カルテン
于 2012-02-28T17:42:00.237 に答える