シータグラフ

Type of geometric spanner graph

計算幾何学において、シータグラフまたは-グラフは、ヤオグラフに似た幾何学的スパナの一種である。基本的な構築方法は、各頂点の周囲の空間を一連の円錐に分割し、それらの円錐自体がグラフの残りの頂点を分割するというものである。ヤオグラフと同様に、-グラフには円錐ごとに最大で1つの辺が含まれるが、その辺の選択方法が異なる。ヤオグラフはグラフの計量空間に従って最も近い頂点を選択するのに対し、-グラフは各円錐内に含まれる固定された光線（通常は円錐の二等分線）を定義し、その光線への直交射影に関して最も近い近傍を選択する。結果として得られるグラフは、いくつかの優れたスパナ特性を示す。[1] Θ {\displaystyle \Theta } Θ {\displaystyle \Theta } Θ {\displaystyle \Theta }

Θ {\displaystyle \Theta } グラフは1987年にClarkson [2]によって初めて記述され、1988年にKeil [3]によって独立に記述されました。

構築

直交投影線から発するグラフの錐の例 Θ {\displaystyle \Theta } p {\displaystyle p} l {\displaystyle l}

Θ {\displaystyle \Theta } -グラフは、その構築を決定するいくつかのパラメータで指定されます。最も明白なパラメータは で、これは各頂点の周囲の空間を分割する等角円錐の数に対応します。特に、頂点 の場合、 についての円錐は、その間の角度が である 2 本の無限光線がそこから放射していると想像できます。 に関して、これらの円錐を から反時計回りのパターンでを通してとラベル付けすることができます。 は通常、その二等分線が平面に対して角度 0 を持つように開きます。これらの円錐が平面を分割するので、グラフの残りの頂点セット (一般的な位置を想定) もに関して から までのセットに分割されます。グラフ内のすべての頂点には、同じ向きの同じ数の円錐があり、それぞれに含まれる頂点のセットについて考えることができます。 k {\displaystyle k} p {\displaystyle p} p {\displaystyle p} θ = 2 π / k {\displaystyle \theta =2\pi /k} p {\displaystyle p} C 1 {\displaystyle C_{1}} C k {\displaystyle C_{k}} C 1 {\displaystyle C_{1}} V 1 {\displaystyle V_{1}} V k {\displaystyle V_{k}} p {\displaystyle p}

単一の円錐を考えるとき、 から発する別の光線を指定する必要があります。この光線を とラベル付けします。 のすべての頂点について、各頂点の への直交射影を考えます。 がそのような射影に最も近い頂点であると仮定すると、 の辺がグラフに追加されます。これが、常に最も近い頂点を選択する Yao グラフとの主な違いです。例の画像では、 Yao グラフでは ではなく の辺が含まれます。 p {\displaystyle p} l {\displaystyle l} V i {\displaystyle V_{i}} v ∈ V i {\displaystyle v\in V_{i}} l {\displaystyle l} r {\displaystyle r} { p , r } {\displaystyle \{p,r\}} { p , q } {\displaystyle \{p,q\}}

グラフの構築は時間内のスイープラインアルゴリズムで可能である。[1] Θ {\displaystyle \Theta } O ( n log ⁡ n ) {\displaystyle O(n\log {n})}

特性

Θ {\displaystyle \Theta } グラフはいくつかの優れた幾何学的スパナ特性 を示します

パラメータが定数の場合、グラフは疎なスパナです。各円錐は最大で1つの辺を生成するため、ほとんどの頂点の次数は小さくなり、グラフ全体の辺数は最大で になります。 k {\displaystyle k} Θ {\displaystyle \Theta } k ⋅ n = O ( n ) {\displaystyle k\cdot n=O(n)}

スパナ内の任意の2点間の伸縮係数は、それらの計量空間距離とスパナ内（つまり、スパナの次の辺から）の距離との比として定義されます。スパナ全体の伸縮係数は、スパナ内のすべての点のペアにおける最大の伸縮係数です。上で述べたように、のとき、 のグラフの伸縮係数は最大 です。[1]各円錐の直交投影線を二等分線として選択すると、 のとき、スパニング比は最大 です。[4] θ = 2 π / k {\displaystyle \theta =2\pi /k} k ≥ 9 {\displaystyle k\geq 9} Θ {\displaystyle \Theta } 1 / ( cos ⁡ θ − sin ⁡ θ ) {\displaystyle 1/(\cos \theta -\sin \theta )} l {\displaystyle l} k ≥ 7 {\displaystyle k\geq 7} 1 / ( 1 − 2 sin ⁡ ( π / k ) ) {\displaystyle 1/(1-2\sin(\pi /k))}

の場合、グラフは最近傍グラフを形成する。 の場合、各頂点は左側の何か、右側の何か（もし存在する場合）に接続するため、グラフが連結であることは容易に分かる。[5]、[6]、[7]、[8]、[4]の場合、グラフは連結であることが知られている。これらの結果の多くは、そのスパニング比の上限および／または下限も与えている。 k = 1 {\displaystyle k=1} Θ {\displaystyle \Theta } k = 2 {\displaystyle k=2} k = 3 {\displaystyle k=3} 4 {\displaystyle 4} 5 {\displaystyle 5} 6 {\displaystyle 6} ≥ 7 {\displaystyle \geq 7} Θ {\displaystyle \Theta }

が偶数の場合、半グラフと呼ばれるグラフの変形を作成できます。半グラフでは、円錐自体が偶数と奇数の集合に交互に分割され、辺は偶数円錐（または奇数円錐）のみで考慮されます。半グラフには、独自の優れた特性があることが知られています。例えば、半グラフ（および、結果として、2つの相補的な半グラフの和であるグラフ）は、2-スパナーであることが知られています。[8] k {\displaystyle k} Θ k {\displaystyle \Theta _{k}} Θ k {\displaystyle \Theta _{k}} Θ k {\displaystyle \Theta _{k}} Θ 6 {\displaystyle \Theta _{6}} Θ 6 {\displaystyle \Theta _{6}} Θ 6 {\displaystyle \Theta _{6}}

シータグラフを描くためのソフトウェア

  • Javaで書かれたツール
  • 計算幾何学アルゴリズムライブラリ (CGAL) の円錐ベーススパナ

参照

参考文献

  1. ^ abc Narasimhan, Giri; Smid, Michiel (2007), Geometric Spanner Networks , Cambridge University Press , ISBN 978-0-521-81513-0。
  2. ^ K. Clarkson. 1987. 最短経路動作計画のための近似アルゴリズム。第19回ACMコンピューティング理論シンポジウム（STOC '87）の議事録、Alfred V. Aho（編）ACM、ニューヨーク州ニューヨーク、米国、56-65ページ
  3. ^ Keil, J. (1988). 完全ユークリッドグラフの近似. SWAT 88, 208–213.
  4. ^ ab Ruppert, J., & Seidel, R. (1991). d次元完全ユークリッドグラフの近似. Proc. 3rd Canad. Conf. Comput. Geom (pp. 207–210).
  5. ^ アイヒホルツァー、オズウィン;ペ・サンウォン;バルバ、ルイス。ボーズ、プロセンジット。コーマン、マティアス。ファン・レンセン、アンドレ。タスラキアン、ペルーズ。 Verdonschot、Sander (2014 年 10 月)、「Theta-3 is Connected」、Computational Geometry、47 (9): 910–917、arXiv : 1404.7186、doi : 10.1016/j.comgeo.2014.05.001
  6. ^ バーバ、ルイス;ボーズ, プロセンジット;ド・カルフェル、ジャン＝ルー。ファン・レンセン、アンドレ。 Verdonschot、Sander (2013)、「Theta-4 グラフのストレッチ係数について」、アルゴリズムとデータ構造、コンピューター サイエンスのレクチャー ノート、vol. 8037、ハイデルベルク: Springer、pp.  109–120、arXiv : 1303.5473、doi : 10.1007/978-3-642-40104-6_10、ISBN 978-3-642-40103-9、MR  3126350。
  7. ^ ボーズ、プロセンジット;パット・モーリン;ファン・レンセン、アンドレ。 Verdonschot、Sander (2015)、「The θ 5 -graph is a spaner」、Computational Geometry、48 (2): 108–119、arXiv : 1212.0570、doi : 10.1016/j.comgeo.2014.08.005、MR  3260251。
  8. ^ ab Bonichon, N., Gavoille, C., Hanusse, N., & Ilcinkas, D. (2010). シータグラフ、ドロネー三角形分割、直交面間の接続. 『コンピュータサイエンスにおけるグラフ理論的概念』（pp. 266–278）. Springer Berlin/Heidelberg.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Theta_graph&oldid=1299442643"