貪欲な幾何学スパナ

計算幾何学において、グリーディ幾何学的スパナーは、ユークリッド空間内の有限個の点間の距離がユークリッド距離に近似する無向グラフである。グラフの頂点はこれらの点を表す。スパナーのエッジは、2つの端点がより短いエッジの短いパスで接続されていない場合にエッジを含めるグリーディアルゴリズムによって選択される。グリーディスパナーは、Gautam Dasの博士論文^{[ 1 ]}および会議論文^{[ 2 ]} 、その後Ingo Althöferらによるジャーナル論文^{[ 3 ]}で初めて記述された。これらの資料では、Marshall Bern (未発表) が同じ構成を独自に発見したともされている。

貪欲な幾何学的スパナーは、次数が制限され、辺の総数が線形であり、総重みがユークリッド最小全域木に近い。既知の構築方法は遅いが、同様の特性を持つ高速近似アルゴリズムが知られている。^{[ 4 ]}

貪欲な幾何学的スパナーは、点の集合とパラメータからなる入力から決定される。$t ≥ 1$目標は、最短経路距離が最大でも のグラフを構築することです。${\displaystyle t}$点のペア間の幾何学的距離の倍数。点を頂点とするエッジのないグラフから始めて、エッジを1つずつ追加していく貪欲アルゴリズムによって構築できます。すべての点のペアは、最も近いペアから始めて、距離の昇順でソートされて考慮されます。各ペアについて${\displaystyle (u,v)}$点の 1 つから、アルゴリズムはこれまでに構築されたグラフにすでにパスが含まれているかどうかをテストします。${\displaystyle u}$に${\displaystyle v}$最大長さ${\displaystyle t\cdot d(u,v)}$そうでない場合は、端${\displaystyle uv}$長さ${\displaystyle d(u,v)}$がグラフに追加されます。構成上、結果として得られるグラフは、最大で伸縮係数が の幾何学的スパナです。${\displaystyle t}$[ ^{3 ]​}

この方法を単純に実装すると時間がかかる${\displaystyle O(n^{3}\log n)}$入力に対して${\displaystyle n}$ポイント。これは、各ポイントの考慮事項が${\displaystyle O(n^{2})}$点のペアは、グラフ内の最短経路を見つけるためのダイクストラ法のインスタンスを含みます。${\displaystyle O(n)}$エッジを使用します。${\displaystyle O(n^{2})}$点のペアのソート済みリストを格納するためのスペース。より高度なアルゴリズムでは、同じグラフを時間内に構築できます。${\displaystyle O(n^{2}\log n)}$[ ^{5 ]}または宇宙空間^で${\displaystyle O(n)}$^{[ 6 ]} グラフクラスタリングを使用してグラフ距離を迅速に近似するグリーディスパナーの変種の構成は、${\displaystyle O(n\log n)}$任意の有界次元のユークリッド空間において、貪欲スパナーと（ほぼ）同じ性質を持つスパナーを生成することができる。^{[ 7 ] [ 8 ]}同じ方法は、有界倍増次元を持つ空間にも拡張できる。^{[ 4 ]}

同じ貪欲な構成法は任意の距離空間でスパナーを生成するが、ユークリッド空間では、より一般的には成り立たないいくつかの優れた性質を持つ。^{[ 4 ]}

任意の距離空間における貪欲な幾何学的スパナーは、常にその入力の最小全域木を含みます。これは、貪欲な構築アルゴリズムが、最小全域木に対するクラスカルのアルゴリズムと同じエッジの挿入順序に従うためです。貪欲なスパナーアルゴリズムとクラスカルのアルゴリズムを並列に実行し、同じ頂点のペアを同じ順序で考慮すると、クラスカルのアルゴリズムによって追加された各エッジは、貪欲なスパナーアルゴリズムによっても追加されます。これは、エッジの端点が既にパスで接続されていないためです。極限の場合、${\displaystyle t}$十分に大きい（例：${\displaystyle t>n}$、 どこ${\displaystyle n}$（はグラフの頂点の数）2つのアルゴリズムは同じ出力を生成します。^{[ 3 ]}

次元が制限されたユークリッド空間では、任意の定数に対して${\displaystyle t}$貪欲な幾何学${\displaystyle t}$-スパナのセット${\displaystyle n}$点は次数が制限されているので、次のことも${\displaystyle O(n)}$エッジ。^{[ 9 ] [ 10 ] [ 7 ]}この性質は、良好なメトリック空間にも適用されません。貪欲スパナーの頂点次数が無限大となる、倍増次元が有界な空間が存在します。 ^{[ 4 ] [ 11 ] [ 12 ]}しかし、そのような空間では、エッジの数は依然として${\displaystyle O(n)}$[ ^{4 ]​}

次元が制限されたユークリッド空間における貪欲な幾何学的スパナーの総重量は、ユークリッド最小全域木の総重量の最大定数倍である。^{[ 9 ] [ 10 ] [ 7 ]} この性質は、倍増次元が制限された空間でも成り立つ。^{[ 4 ]}