相対的近隣グラフ

計算幾何学において、相対近傍グラフ(RNG ) は、ユークリッド平面上の点の集合上で、2 つの点を辺で結び、その 2 つの点と2つの点の間よりも 2 つの点に近い3 番目の点が存在しない場合は、それらの点を辺で結ぶことによって定義される無向グラフです。このグラフは、 1980 年にGodfried Toussaintによって、集合の形状に対する人間の認識と一致する構造を点の集合から定義する方法として提案されました。^[1]^[2] $p$ $q$ $r$ $p$ $q$

アルゴリズム

Supowit (1983) は、平面上の点の相対近傍グラフを時間内に効率的に構築する方法を示した。^{[3]これは、}単位正方形内に均一に分布するランダムな点の集合に対して、期待時間で計算できる。^[4]相対近傍グラフは、点集合のDelaunay 三角形分割から線形時間で計算できる。 ^[5]^[6] $n$ $O(n\log n)$ $O(n)$

一般化

相対近傍グラフは点間の距離のみで定義されるため、任意の次元の点集合に対して定義することができ、^[1]^[7]^[8]、非ユークリッド距離に対しても定義することができる。^[1]^[5]^[9]^[10]高次元の点集合に対する相対近傍グラフの計算は、時間で行うことができる。 $O(n^{2})$

参考文献

^ abc Toussaint, GT (1980)、「有限平面集合の相対近傍グラフ」、パターン認識、12 (4): 261– 268、doi :10.1016/0031-3203(80)90066-7。
^ Jaromczyk, JW; Toussaint, GT (1992)、「相対近傍グラフとその関連」、IEEE 論文集、80 (9): 1502– 1517、doi :10.1109/5.163414。
^ Supowit, KJ (1983)、「相対近傍グラフと最小全域木への応用」、Journal of the ACM、30 (3): 428– 448、doi : 10.1145/2402.322386。
^ カタジャイネン、ジルキ;ネバライネン、オリ。 Teuhola、Jukka (1987)、「平面相対近傍グラフを計算するための線形期待時間アルゴリズム」、Information Processing Letters、25 (2): 77–86、doi :10.1016/0020-0190(87)90225-0。
^ ab Jaromczyk, JW; Kowaluk, M. (1987)、「相対近傍グラフに関する注記」、Proc. 3rd Symp. Computational Geometry、ニューヨーク、NY、米国: ACM、pp. 233– 241、doi :10.1145/41958.41983、ISBN 0-89791-231-4。
^ Lingas, A. (1994)、「ドロネー三角形分割による相対近傍グラフの線形時間構築」、計算幾何学、4 (4): 199– 208、doi : 10.1016/0925-7721(94)90018-3。
^ Jaromczyk, JW; Kowaluk, M. (1991)、「3次元ユークリッド空間における相対近傍グラフの構築」、離散応用数学、31 (2): 181– 191、doi : 10.1016/0166-218X(91)90069-9。
^ Agarwal, Pankaj K. ; Mataušek, Jiří (1992)、「3 次元の相対近傍グラフ」、Proc. 3rd ACM–SIAM Symp. Discrete Algorithms、pp. 58– 65。
^ O'Rourke, J. (1982)、「およびメトリックにおける相対近傍グラフの計算」、パターン認識、15 (3): 189– 192、doi :10.1016/0031-3203(82)90070-X $L_{1}$ $L_{\infty}$ 。
^ Lee, DT (1985)、「-metric における相対近傍グラフ」、パターン認識、18 (5): 327– 332、doi :10.1016/0031-3203(85)90023-8 $L_{1}$ 。
^ Urquhart, RB (1980)、「相対近傍グラフの計算アルゴリズム」、Electronics Letters、16 (14): 556– 557、doi :10.1049/el:19800386。
^ Toussaint, GT (1980)、「コメント: 相対近傍グラフを計算するためのアルゴリズム」、Electronics Letters、16 (22): 860、doi :10.1049/el:19800611アーカートによる返答、860～861ページ。
^ アンドラーデ、ディオゴ・ヴィエイラ; de Figueiredo、Luiz Henrique (2001)、「相対近傍グラフの適切な近似」(PDF)、Proc.第 13 回カナダ計算幾何学会議。

[t80-1] Toussaint, GT (1980)、「有限平面集合の相対近傍グラフ」、パターン認識、12 (4): 261– 268、doi :10.1016/0031-3203(80)90066-7。

[2] Jaromczyk, JW; Toussaint, GT (1992)、「相対近傍グラフとその関連」、IEEE 論文集、80 (9): 1502– 1517、doi :10.1109/5.163414。

[3] Supowit, KJ (1983)、「相対近傍グラフと最小全域木への応用」、Journal of the ACM、30 (3): 428– 448、doi : 10.1145/2402.322386。

[4] カタジャイネン、ジルキ;ネバライネン、オリ。 Teuhola、Jukka (1987)、「平面相対近傍グラフを計算するための線形期待時間アルゴリズム」、Information Processing Letters、25 (2): 77–86、doi :10.1016/0020-0190(87)90225-0。

[jk87-5] Jaromczyk, JW; Kowaluk, M. (1987)、「相対近傍グラフに関する注記」、Proc. 3rd Symp. Computational Geometry、ニューヨーク、NY、米国: ACM、pp. 233– 241、doi :10.1145/41958.41983、ISBN 0-89791-231-4。

[6] Lingas, A. (1994)、「ドロネー三角形分割による相対近傍グラフの線形時間構築」、計算幾何学、4 (4): 199– 208、doi : 10.1016/0925-7721(94)90018-3。

[7] Jaromczyk, JW; Kowaluk, M. (1991)、「3次元ユークリッド空間における相対近傍グラフの構築」、離散応用数学、31 (2): 181– 191、doi : 10.1016/0166-218X(91)90069-9。

[8] Agarwal, Pankaj K. ; Mataušek, Jiří (1992)、「3 次元の相対近傍グラフ」、Proc. 3rd ACM–SIAM Symp. Discrete Algorithms、pp. 58– 65。

[9] O'Rourke, J. (1982)、「およびメトリックにおける相対近傍グラフの計算」、パターン認識、15 (3): 189– 192、doi :10.1016/0031-3203(82)90070-X $L_{1}$ $L_{\infty}$ 。

[10] Lee, DT (1985)、「-metric における相対近傍グラフ」、パターン認識、18 (5): 327– 332、doi :10.1016/0031-3203(85)90023-8 $L_{1}$ 。

[11] Urquhart, RB (1980)、「相対近傍グラフの計算アルゴリズム」、Electronics Letters、16 (14): 556– 557、doi :10.1049/el:19800386。

[12] Toussaint, GT (1980)、「コメント: 相対近傍グラフを計算するためのアルゴリズム」、Electronics Letters、16 (22): 860、doi :10.1049/el:19800611アーカートによる返答、860～861ページ。

[13] アンドラーデ、ディオゴ・ヴィエイラ; de Figueiredo、Luiz Henrique (2001)、「相対近傍グラフの適切な近似」(PDF)、Proc.第 13 回カナダ計算幾何学会議。

アルゴリズム

一般化

関連グラフ

参考文献