可視性グラフ

計算幾何学とロボットの 動作計画において、^[1]可視性グラフは、一般的にはユークリッド平面上の点と障害物の集合に対する相互可視位置のグラフです。グラフ内の各ノードは点の位置を表し、各エッジはそれらの間の可視接続を表します。つまり、2つの位置を結ぶ線分が障害物を通過しない場合は、グラフ内でそれらの間をエッジが描画されます。位置の集合が直線上にある場合、これは順序付けられたシリーズとして理解できます。そのため、可視性グラフは時系列分析の領域にまで拡張されています。

可視グラフは、平面上の多角形障害物のセットの間でユークリッド最短経路を見つけるために使用できます。2つの障害物間の最短経路は、障害物の頂点を除いて直線セグメントをたどり、障害物の頂点で曲がる可能性があるため、ユークリッド最短経路は、開始点と目的地点、および障害物の頂点をノードとする可視グラフ内の最短経路です。^{[2]したがって、ユークリッド最短経路問題は、可視グラフの構築と、}ダイクストラ法などの最短経路アルゴリズムをグラフに適用するという、2つのより単純なサブ問題に分解できます。障害物と比較して無視できないサイズを持つロボットの動作を計画する場合、ロボットのサイズを補正するために障害物を拡張した後、同様のアプローチを使用できます。^[2]ロザノ・ペレスとウェズリー（1979）は、ユークリッド最短経路の可視グラフ法を、1969年にニルス・ニルソンがロボットシェーキーの動作計画について行った研究に帰し、また、1973年にロシアの数学者MBイグナティエフ、FMクラコフ、AMポクロフスキーが行ったこの方法の説明も引用している。

可視性グラフは、無線アンテナの配置を計算するために使用したり、可視性グラフ分析を通じて建築や都市計画内で使用されるツールとして使用したりすることもできます。

一直線上に位置する一連の位置の可視性グラフは、時系列のグラフ理論的表現として解釈することができます。^{[3]この特定のケースは}、時系列、動的システム、グラフ理論の間に橋を架けます。

単純な多角形の可視グラフでは、多角形の頂点が点の位置となり、多角形の外部が唯一の障害物となる。単純な多角形の可視グラフはハミルトングラフでなければならない。つまり、多角形の境界は可視グラフ内でハミルトン閉路を形成する。すべての可視グラフが単純な多角形を誘導するわけではないことは知られている。しかし、単純な多角形の可視グラフの効率的なアルゴリズムによる特徴付けは未だにわかっていない。これらのグラフは、多くの既知のよく構造化されたグラフの族には当てはまらない。つまり、完全グラフ、円グラフ、弦グラフではない可能性がある。^{[4]この現象の例外は、単純な多角形の可視グラフが}cop-win グラフであることだ。^[5]

アートギャラリー問題とは、障害物以外のすべての点がこの集合から見えるような点の小さな集合を見つける問題です。アート ギャラリー問題の特定の形式は、可視性グラフ内の 支配集合を見つけることとして解釈できます。

多角形または曲線のシステムの二重接線は、接触点でそれらを貫通することなく、2 つの多角形または曲線に接する線です。多角形の集合の二重接線は、多角形の頂点をノードとして、多角形自体を障害物とする可視性グラフのサブセットを形成します。ユークリッド最短経路問題に対する可視性グラフ アプローチは、すべての可視エッジを使用する代わりに二重接線からグラフを形成することで高速化できます。これは、ユークリッド最短経路が障害物の境界に出入りできるのは二重接線に沿ってのみであるためです。^[6]

• 可視性グラフ分析
• ファジー建築空間分析
• スペース構文

• デ・バーグ、マーク。マーク・ヴァン・クレフェルト。マーク・オーヴァーマーズ; Schwarzkopf、Otfried (2000)、「第 15 章: 可視性グラフ」、計算幾何学(第 2 版)、Springer-Verlag、pp. 307–317、ISBN 978-3-540-65620-3。
• ロザノ・ペレス、トマス; ウェズリー、マイケル A. (1979)、「多面体障害物間の衝突のない経路を計画するためのアルゴリズム」、Communications of the ACM、22 (10): 560–570、doi : 10.1145/359156.359164、S2CID  17397594。

• VisiLibity: 浮動小数点可視性アルゴリズムとサポートされるデータ型の無料オープン ソース C++ ライブラリ。このソフトウェアは、多角形の穴がある多角形環境の可視性グラフを計算するために使用できます。Matlab インターフェイスも含まれています。