セミヤオグラフ

n個の物体集合Pのk-半ヤオグラフ（k -SYG ）は幾何学的近接グラフであり、運動物体上の最近傍点すべての維持のための運動データ構造を提示するために最初に記述された。^[1]これはアンドリュー・ヤオにちなんで名付けられたヤオグラフとの関係から名付けられている。

工事

k -SYGは次のように構築されます。P内の各点pの周囲の空間は、開角の多面体円錐の集合に分割されます。これは、頂点から発する多面体円錐内の各光線の角度が最大であり、pは円錐軸への投影が最小となる各多面体円錐内の Pのk点に接続していることを意味します。 $\theta$ $\theta$

プロパティ

k = 1のk - SYGはシータグラフとして知られ、2つのドロネー三角形分割の和集合である。^[2]
小さく適切な円錐軸に対して、k -SYGはk -近傍グラフ（k -NNG）のスーパーグラフを与える。 ^[3]^[4]例えば2次元では、各点の周りの平面を等角の6つのくさびに分割し、円錐の二等分線の方向に円錐軸を取ると、k -NNGのスーパーグラフとしてk -SYGが得られる。 $\theta$

参照

幾何学的なスパナ

参考文献

^ Rahmati, Zahed (2014). シンプルで高速なキネティックデータ構造(PDF) (論文). ビクトリア大学.
^ Bonichon, N.; Gavoille, C.; Hanusse, N.; Ilcinkas, D. (2010). 「シータグラフ、ドロネー三角形分割、直交面間の接続」『コンピュータサイエンスにおけるグラフ理論的概念』pp. 266– 278.
^ Rahmati, Z.; Abam, MA; King, V .; Whitesides, S .; Zarei, A. (2015). 「運動学的近接問題のためのシンプルで高速な手法」.計算幾何学. 48 (4): 342– 359. arXiv : 1311.2032 . doi : 10.1016/j.comgeo.2014.12.002 .
^ Rahmati, Z.; Abam, MA; King, V .; Whitesides, S. (2019). 「キネティックk-セミヤオグラフとその応用」.計算幾何学. 77 : 10–26 . arXiv : 1412.5697 . doi :10.1016/j.comgeo.2015.11.001.

[rmt1-1] Rahmati, Zahed (2014). シンプルで高速なキネティックデータ構造(PDF) (論文). ビクトリア大学.

[bonichon_etal-2] Bonichon, N.; Gavoille, C.; Hanusse, N.; Ilcinkas, D. (2010). 「シータグラフ、ドロネー三角形分割、直交面間の接続」『コンピュータサイエンスにおけるグラフ理論的概念』pp. 266– 278.

[rmt2-3] Rahmati, Z.; Abam, MA; King, V .; Whitesides, S .; Zarei, A. (2015). 「運動学的近接問題のためのシンプルで高速な手法」.計算幾何学. 48 (4): 342– 359. arXiv : 1311.2032 . doi : 10.1016/j.comgeo.2014.12.002 .

[rmt3-4] Rahmati, Z.; Abam, MA; King, V .; Whitesides, S. (2019). 「キネティックk-セミヤオグラフとその応用」.計算幾何学. 77 : 10–26 . arXiv : 1412.5697 . doi :10.1016/j.comgeo.2015.11.001.