Urquhart graph とは

計算ジオメトリでは、Roderick B. Urquhartにちなんで命名された、飛行機内の点の集合のUrquhartグラフは、Delaunay三角測量の各三角形から最長の辺を削除して得られます。
Urquhartグラフ(Urquhart(1980))は、Delaunayの各三角形から最も長い辺を削除することは、相対近傍グラフを構成する高速な方法であることを示唆しています。相互に比べてpとqの両方に近い点r)。 Delaunay三角測量は時間O(n log n)で構築できるので、Urquhartグラフについても同じ時間範囲が保持されます。 Urquartグラフは、相対近傍グラフとまったく同じではないことが後で示されましたが、それを良い近似として使用することができます。 Urquhartグラフと相対近傍グラフとの間の不一致によって残されたO(n log n)時間における相対近傍グラフを構築する問題は、Supowit(1983)によって解決された。
相対近傍グラフと同様に、一般的な位置にある一連の点のUrquartグラフには、その点のユークリッド最小スパニングツリーが含まれており、そこから接続グラフになります。