Yao graph とは

計算幾何学では、Andrew Yaoにちなんで命名されたYaoグラフは幾何学的なスパンの一種であり、幾何学的な点の集合をその特性と結びつける重み付けされた無向グラフであり、グラフの各対の点について、ユークリッド距離の一定の要素内にある。
2次元Yaoグラフの根底にある基本的な考え方は、与えられた点のそれぞれを等間隔の線で囲み、等角度のセクタに分割し、各点をこれらの各セクタの最も近い隣に接続することです。 Yaoグラフには、上記の光線とセクタの数である整数パラメータk≧6が関連付けられています。 kの値が大きいほどユークリッド距離に近い近似が得られます。ストレッチ係数はせいぜい 1 / ( cos θ sin θ ) {\displaystyle 1/(\cos \theta -\sin \theta )} で、 θ {\displaystyle \theta } はセクタの角度です。同じ考え方を2つ以上の次元でポイントセットに拡張することもできますが、必要なセクタの数は次元とともに指数関数的に増加します。
Andrew Yaoはこれらのグラフを使用して、高次元のユークリッド最小スパニングツリーを構築しました。