相対的近隣グラフ

単位正方形内のランダムな 100 個のポイントの相対的な近傍グラフ。

計算幾何学において、相対近傍グラフ（RNG）とは、ユークリッド平面上の点集合において、2点を辺で結ぶことで定義される無向グラフである。RNGは、2点から3点までの距離が互いに近く、かつ2点から3点までの距離よりも短い場合に、2点を辺で結ぶことで定義される。このグラフは、人間の知覚に一致する点集合の構造を定義する方法として、1980年にゴッドフリード・トゥーサンによって提唱された。 ^{[1] [2]}${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle r}$ ${\displaystyle p}$ ${\displaystyle q}$

アルゴリズム

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

一般化

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

関連グラフ

相対近傍グラフは、レンズベースのベータスケルトンの一例です。これはドロネー三角形分割のサブグラフです。また、ユークリッド最小全域木はそのサブグラフであり、したがって連結グラフであることがわかります。

アーカートグラフは、ドロネー三角形分割における各三角形から最長の辺を削除して形成されるグラフであり、もともと相対近傍グラフを計算するための高速な方法として提案されました。^[11]アーカートグラフは相対近傍グラフと異なる場合がありますが^[12]、相対近傍グラフの近似値として使用できます。^[13]

参考文献

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。
5. Jaromczyk, JW; Kowaluk, M. (1987), "A note on relative neighbor graphs", Proc. 3rd Symp. Computational Geometry , New York, NY, USA: 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${\displaystyle L_{1}}$ ${\displaystyle L_{\infty}}$ 。
10. Lee, DT (1985)、「-metricにおける相対近傍グラフ」、パターン認識、18 (5): 327– 332、doi :10.1016/0031-3203(85)90023-8${\displaystyle 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. Andrade, Diogo Vieira; de Figueiredo, Luiz Henrique (2001)、「相対近傍グラフの良好な近似値」(PDF)、Proc. 13th Canadian Conference on Computational Geometry、2019年3月28日時点のオリジナルよりアーカイブ、 2024年3月24日取得。