ユークリッド最小全域木

ユークリッド最小全域木の2つの辺が頂点で交わる場合、それらの角度は60°以上でなければならず、正三角形の2辺を形成する場合にのみ等しくなります。これは、2つの辺がそれよりも鋭角を形成する場合、2つの辺のうちの1つを、それらが形成する三角形の3番目の短い辺に置き換えることができ、全長が短い木を形成できるためです。^{[ 14 ]}これに対し、シュタイナー木の問題では角度の制約がより厳しく、最適なシュタイナー木ではすべての角度が少なくとも120°になります。^{[ 12 ]}

同じ 60° の角度制限は、ユークリッド空間において、接点を超えて 2 つの球が交差することなく、中心の単位球に接することができる単位球の最大数を求めるキッシング数問題にも現れます。これらの球の中心点は、星形の最小全域木を持ち、中心点は他のすべての点に隣接しています。逆に、任意の頂点に対して${\displaystyle v}$任意の最小全域木では、中心が${\displaystyle v}$そして各辺に沿って2単位の点では、各隣接点に対して接線が${\displaystyle v}$したがって、${\displaystyle n}$次元空間において、頂点の最大次数（それに接続されている全域木の辺の数）は、球の接吻数に等しい。${\displaystyle n}$次元。^{[ 15 ]}平面最小全域木の次数は最大で6であり、木の次数が6の場合、次数が最大で5の別の最小全域木が必ず存在する。^{[ 7 ]} 3次元最小全域木の次数は最大で12である。^{[ 15 ]}キッシング数の正確な値がわかっている高次元は、4次元、8次元、および24次元のみである。^{[ 16 ]}

与えられた連続分布からランダムに生成された点の場合、最小全域木はほぼ確実に一意です。任意の次数を持つ頂点の数は、頂点の数が多い場合、その頂点の数の定数倍に収束します。これらの定数の値は、次数と分布に依存します。しかし、単位正方形内に均一に分布する点の葉の数のような単純な場合でさえ、その正確な値はわかりません。^{[ 17 ]}

エッジ${\displaystyle uv}$任意のユークリッド最小全域木において、2 つの円を交差させることによって形成されるレンズ(またはvesica piscis ) は、${\displaystyle uv}$半径には他の頂点は存在しないため${\displaystyle w}$その内部に。言い換えれば、木に端がある場合${\displaystyle uv}$そのレンズには第3の点が含まれている${\displaystyle w}$ならば、それは最小の長さではない。なぜなら、2つの円の幾何学により、${\displaystyle w}$どちらにもより近い${\displaystyle u}$そして${\displaystyle v}$彼らがお互いに対して持っているものよりも。${\displaystyle uv}$木から取り除かれ、${\displaystyle w}$のいずれかとつながり続けるだろう${\displaystyle u}$そして${\displaystyle v}$片方はそうではないが、もう片方はそうではない。${\displaystyle uv}$による${\displaystyle uw}$または${\displaystyle vw}$（これらの2つのエッジのうちどちらが再接続しても）${\displaystyle w}$切断された頂点まで）より短い木が生成されるだろう。^{[ 12 ]}

エッジ${\displaystyle uv}$任意のユークリッド最小全域木のうち、60°と120°の角度を持つ菱形は、${\displaystyle uv}$その長い対角線は、他のすべての辺によって同様に形成される菱形とは互いに分離している。 端点を共有する 2 つの辺は、菱形が重なることはない。なぜなら、それは 60° より鋭い辺の角度を意味するからである。また、互いに分離している 2 つの辺は、菱形が重なることはない。もし重なる場合、同じ 4 つの頂点間で、2 つの辺のうち長い方の辺を短い辺に置き換えることができるからである。^{[ 12 ]}

特定の幾何学的グラフは、点集合内の空領域を含む定義を持ち、そこから、ユークリッド最小全域木の一部となり得るすべての辺が含まれることが導かれる。これらには以下が含まれる。

• 相対近傍グラフとは、定義するレンズが空である場合に、任意の2点間にエッジが存在するグラフである。
• ガブリエルグラフとは、任意の2点間に辺が存在するグラフであり、その2点を直径とする円が空である場合に限り、その2点間に辺が存在する。
• ドロネー三角形分割とは、任意の2点間に、その2点を弦とする空の円が存在する場合に、その2点間に辺が存在する分割のことである。
• ウルクハートグラフは、デローネ三角形分割から各三角形の最長辺を取り除くことによって形成される。残った各辺について、その辺を使用するデローネ三角形の頂点は、相対的な近傍グラフの空の三日月領域内に存在してはならない。

これらのグラフの空領域基準は段階的に弱くなるため、これらのグラフは部分グラフの順序付きシーケンスを形成します。つまり、エッジ間の部分集合関係を「⊆」で表すと、これらのグラフは次の関係を持ちます。

最小全域木を含むことが保証されているもう 1 つのグラフはYao グラフです。これは、平面上の各点の周囲を 6 つの 60° の扇形に分割し、各扇形内の各点を最も近い隣接点に接続することによって、平面上の点に対して決定されます。結果として得られるグラフには相対近傍グラフが含まれます。これは、空のレンズを持つ 2 つの頂点が、それぞれの扇形内で互いに最も近い隣接点である必要があるためです。上記の他の多くの幾何学的グラフと同様に、この定義はより高次元に一般化することができ、(Delaunay 三角形分割とは異なり) その一般化には常に線形数のエッジが含まれます。^{[ 20 ] [ 21 ]}

のために${\displaystyle n}$単位正方形（またはその他の固定形状）内の点において、最小全域木の辺の全長は${\displaystyle O({\sqrt {n}})}$等間隔に配置された点などの点の集合$\displaystyle {\sqrt {n}}\times {\sqrt {n}}$グリッドでは、この境界を達成します。^{[ 12 ]}単位超立方体内の点については、${\displaystyle d}$次元空間では、対応する境界は${\displaystyle O(n^{(d-1)/d})}$^{[ 22 ]}最小全域木の期待される全長にも同じ上限が適用されます。${\displaystyle n}$単位正方形または単位超立方体から均一かつ独立に選択された点。^{[ 23 ]}単位正方形に戻ると、最小全域木の辺の長さの二乗の合計は次のようになる。${\displaystyle O(1)}$この境界は、辺が互いに分離した菱形を持ち、その面積が辺の長さの二乗に比例するという観察から導かれる。${\displaystyle O({\sqrt {n}})}$全長の上限はコーシー・シュワルツの不等式を適用することで得られる。^{[ 12 ]}

これらの結果の別の解釈は、単位正方形内の任意の点の集合の平均辺の長さが${\displaystyle O(1/{\sqrt {n}})}$最大で規則的なグリッド内の点の間隔に比例し、単位正方形内のランダムな点の平均長さは${\displaystyle 1/{\sqrt {n}}}$しかし、ランダムなケースでは、高い確率で最長辺の長さは約$${\displaystyle {\sqrt {\frac {\log n}{\pi n}}},}$$平均よりも一定ではない係数だけ長い。高い確率で、最長の辺は全域木の葉を形成し、他のすべての点から遠く離れた点を最も近い隣接点に接続します。点の数が多い場合、期待値を中心とした最長辺の長さの分布はガンベル分布に収束します。^{[ 24 ]}

最短経路がユークリッド距離に近似する完全幾何グラフの部分グラフである任意の幾何スパナーは、少なくとも最小全域木と同じ長さの辺の総長を持つ必要があり、幾何スパナーの標準的な品質尺度の1つは、同じ点に対する最小全域木の長さと、その長さの比です。貪欲幾何スパナーなど、スパナーを構築するいくつかの方法は、この比の定数上限を達成します。^{[ 13 ]}平面上の同じ点の集合に対する最小全域木とシュタイナー木の長さの比の最大値であるシュタイナー比は、$2/√3 ≈ 1.1547$正三角形の3点の比率。^{[ 12 ]}

ユークリッド最小全域木のすべての辺を、その中点に新しい点を追加することによって細分化すると、結果として得られる木は、拡張された点集合の最小全域木になります。この細分化プロセスを繰り返すことで、ユークリッド最小全域木を任意に細かく細分化できます。ただし、一部の辺のみを細分化したり、辺を中点以外の点で細分化したりすると、細分化された木が最小全域木にならないような点集合が生成される可能性があります。^{[ 25 ]}

平面上の点の最小全域木をより速く見つける方法として、それがドロネー三角形分割の部分グラフであるという性質を利用する方法がある。

1. デローネ三角形分割を計算します。これは次のように実行できます。${\displaystyle O(n\log n)}$時間。デローネ三角形分割は平面グラフであるため、最大で${\displaystyle 3n-6}$端。
2. 各辺にその（二乗した）長さを記入してください。
3. グラフ最小全域木アルゴリズムを実行します。${\displaystyle O(n)}$エッジ、これには${\displaystyle O(n\log n)}$標準的な最小全域木アルゴリズムのいずれかを使用した場合の時間。

その結果、アルゴリズムは${\displaystyle O(n\log n)}$時間、^{[ 2 ]}特定の計算モデルでは最適（下記参照）。

入力座標が整数で配列インデックスとして使用できる場合、より高速なアルゴリズムが可能になります。デローネ三角形分割は、ランダム化アルゴリズムによって構築できます。${\displaystyle O(n\log \log n)}$予想時間。^{[ 26 ]}さらに、ドロネー三角形分割は平面グラフであるため、アルゴリズムの各段階の後、各コンポーネントのペア間の最もコストの低いエッジ以外をすべて削除するボルーフカのアルゴリズムの変種によって、その最小全域木を線形時間で見つけることができます。^{[ 13 ] [ 27 ]}したがって、このアルゴリズムの合計予想時間は次のようになります。${\displaystyle O(n\log \log n)}$^{[ 26 ]}反対方向には、デローネ三角形分割は、ほぼ線形時間で最小全域木から構築できる。${\displaystyle O(n\log ^{*}n)}$、 どこ$\displaystyle \log ^{*}}$は反復対数を表します。^{[ 28 ]}

この問題は、以下のように一般化することもできます。${\displaystyle n}$ポイント${\displaystyle d}$次元空間$\displaystyle \mathbb {R} ^{d}}$。高次元では、デローネ三角形分割によって決定される接続性（同様に凸包を分割する）${\displaystyle d}$次元単体）には最小全域木が含まれますが、三角形分割には完全グラフが含まれる可能性があります。^{[ 4 ]}したがって、完全グラフの全域木として、またはドロネー三角形分割の全域木としてユークリッド最小全域木を見つけるには、${\displaystyle O(dn^{2})}$時間。3次元の場合、最小全域木は時間で見つけることができます。${\displaystyle O{\bigl (}(n\log n)^{4/3}{\bigr )}}$そして、より大きな次元では、時間の中で $${\displaystyle O\left(n^{2-{\frac {2}{\lceil d/2\rceil +1}}+\varepsilon }\right)}$$ いかなる場合でも${\displaystyle \varepsilon >0}$—完全グラフアルゴリズムとドロネー三角形分割アルゴリズムの2次時間限界よりも高速です。^{[ 4 ]}

高次元最小全域木の最適な時間計算量は未だ不明であるが、^{[ 29 ]}二色最近傍ペアの計算の複雑さと密接に関係している。二色最近傍ペア問題では、入力は 2 つの異なる色 (たとえば、赤と青) が与えられた点の集合である。出力は、可能な限り最小の距離を持つ赤い点と青い点のペアである。このペアは常に最小全域木の辺の 1 つを形成する。したがって、二色最近傍ペア問題は、最小全域木を構築し、その辺をスキャンして最短の赤-青の辺を見つけるのにかかる時間で解決できる。逆に、与えられた点の集合の任意の部分集合の任意の赤-青の色付けに対して、二色最近傍ペアは部分集合の最小全域木の 1 つの辺を生成する。部分集合の彩色シーケンスを慎重に選択し、各部分問題の二色最近傍ペアを見つけることで、最小全域木を、同じ数の点の二色最近傍ペアを見つけるための最適時間に比例した時間で見つけることができる。その最適時間が何であれ。^{[ 4 ] [ 11 ]}

任意の有界次元における一様ランダムな点集合に対して、ヤオグラフ^{[ 20 ]}またはドロネー三角形分割は、期待値線形のエッジ数を持ち、最小全域木を含むことが保証され、期待値線形時間で構築できます。^{[ 21 ] [ 6 ] [ 30 ]}これらのグラフから、グラフ最小全域木のためのランダム化線形時間アルゴリズムを使用することで、最小全域木自体を線形時間で構築できます。^{[ 31 ]}しかし、クラスタ化されたデータからの入力に対するこれらの方法の性能が低いため、アルゴリズム工学の研究者は、やや遅い方法を開発するに至りました。${\displaystyle O(n\log n)}$時間制限があり、ランダムな入力、または距離とクラスタリングがランダムなデータに似ている入力に対して、実世界のデータに対してより優れたパフォーマンスを発揮します。^{[ 8 ] [ 32 ] [ 5 ]}

十分に分離されたペア分解とは、与えられた点のサブセットのペアの族であり、すべての点のペアがこれらのサブセットのペアのいずれかに属し、同じサブセットのペアから得られるすべての点のペアはほぼ同じ長さを持つ。線形数の部分集合と、各部分集合の代表的な点のペアを持つ十分に分離されたペア分解を、時間で見つけることが可能である。${\displaystyle O(n\log n)}$これらの代表ペアによって形成されるグラフの最小全域木は、最小全域木の近似値となります。これらの考え方を用いて、${\displaystyle (1+\varepsilon )}$最小全域木の近似値は以下に記載されています。${\displaystyle O(n\log n)}$時間、定数${\displaystyle \varepsilon }$より正確には、各代表ペアをその同値類内の最も近いペアに近似するように選択し、異なるペアに対してこの近似の精度を注意深く変化させることにより、${\displaystyle \varepsilon }$時間制限内では次のように表すことができます。${\displaystyle O(n\log n+(\varepsilon ^{-2}\log ^{2}{\tfrac {1}{\varepsilon }})n),}$任意の固定寸法に対して。^{[ 33 ]}

ユークリッド最小全域木は、移動または変化する点のシステムに様々な方法で一般化されてきた。

• 点の集合が動的な点の挿入または削除のシーケンスを受ける場合、これらの更新のそれぞれが、点の最小全域木に有限量の変化をもたらします。更新シーケンスが事前にわかっている場合、平面上の点については、各挿入または削除後の変化を時間内に求めることができます。${\displaystyle O(\log ^{2}n)}$挿入または削除ごとに。^{[ 34 ]}更新をオンラインで処理する必要がある場合は、より遅い（ただし依然として多項式対数）${\displaystyle O(\log ^{10}n)}$時間制限は既知である。^{[ 35 ]}問題の高次元バージョンでは、更新ごとの時間は遅くなるが、それでも準線形である。^{[ 36 ]}
• のために${\displaystyle n}$一定速度で直線的に移動する点、またはより一般的な代数運動では、最小全域木は、1 つのエッジが削除され、両方の長さが等しくなる時点で別のエッジが置き換えられる一連の交換によって変化します。^{[ 37 ]}直線運動の場合、変化の数は最大でわずかに大きくなります。${\displaystyle n^{25/9}}$^{[ 38 ]}より一般的な代数的運動については、Davenport–Schinzel シーケンスの理論に基づいて、スワップの数にほぼ 3 乗の上限があります。^{[ 39 ]}
• 最小移動全域木問題は、一定時間間隔で一定速度で直線的に移動する点に関する問題であり、この時間間隔中の任意の瞬間に発生する重みの最大合計を最小化する単一の木を求める問題です。これを正確に計算するのはNP困難ですが、2倍以内の精度で多項式時間で近似できます。^{[ 40 ]}
• 運動学的ユークリッド最小全域木問題は、点が連続的な移動と挿入および削除の両方を受ける場合でも最小全域木を維持できる運動学的データ構造を要求する。いくつかの論文がそのような構造を研究しており、 ^{[ 41 ] [ 42 ] [ 43 ] [ 44 ] [ 45 ]}ほぼ3乗の総時間で、交換回数の上限にほぼ一致する、代数的に移動する点の運動学的構造が知られている。^{[ 44 ]}

漸近的な下限値${\displaystyle \Omega (n\log n)}$ユークリッド最小全域木問題の解は、計算の制限モデルで確立できます。これには、代数的決定木モデルと代数的計算木モデルが含まれます。これらのモデルでは、アルゴリズムは、座標に対して単純な代数計算を実行する特定の制限されたプリミティブを介してのみ入力点にアクセスできます。これらのモデルでは、最も近い点のペアの問題には、${\displaystyle \Omega (n\log n)}$時間で平面最小全域木を構築するアルゴリズムは、${\displaystyle O(n\log n)}$このモデル内では、例えばデローネ三角形分割を用いることで最適解が得られます。^{[ 46 ]}ただし、これらの下限値は、ビット演算や座標に対するテーブルインデックス操作が可能な整数点座標を用いた計算モデルには適用されません。これらのモデルでは、上述のように、より高速なアルゴリズムが可能です。^{[ 26 ]}