ベータスケルトン

計算幾何学および幾何学的グラフ理論において、βスケルトンまたはベータスケルトンは、ユークリッド平面上の点の集合から定義される無向グラフです。2 つの点pとq は、すべての角度prq が数値パラメータβから決定されるしきい値よりも鋭い 場合は常に、エッジで接続されます。

βを正の実数とし、次の式を使って 角度θを計算する。

${\displaystyle \theta ={\begin{cases}\sin ^{-1}{\frac {1}{\beta }},&{\text{if }}\beta \geq 1\\\pi -\sin ^{-1}{\beta },&{\text{if }}\beta \leq 1\end{cases}}}$

平面上の任意の 2 点pとqについて、角度prqがθより大きい 点の集合をR _pqとします。すると、R _{pq は}、 β  ≥ 1 かつθ ≤ π/2 の場合、直径βd ( p , q )を持つ 2 つの開円板の和集合の形をとり、 β  ≤ 1 かつθ ≥ π/2 の場合、直径d ( p , q )/ β を持つ 2 つの開円板の交差集合の形をとります 。β  = 1 のとき、2 つの式は同じ値θ  = π/2 を与え、R _{pq は}直径が pqである単一の開円板の形をとります。

平面上の点の離散集合Sの β スケルトンは、R _pqにSの点が含まれない場合に、 2つの点pとqを辺pqで結ぶ無向グラフです。つまり、βスケルトンは領域R _pqによって定義される空の領域グラフです。^[1] S に、角度prqがθより大きい点r が含まれる場合、pq はβスケルトンの辺ではありません。βスケルトンは、そのような点r が存在しないpqのペアで構成されます。

一部の著者は、 β > 1の空の領域R _{pq は} 2 つのディスクの和集合ではなく、レンズ(この文脈では「ルーン」と呼ばれることが多い)、つまり直径βd ( pq )の 2 つの合同なディスクの交差であり、線分pq が両方のディスクの半径上にあり、点pとq が両方とも交差の境界上にあるという別の定義を使用しています。円ベースのβスケルトンと同様に、ルーンベースのβスケルトンには、領域R _pqに他の入力点がない場合は常にエッジpqがあります。この別の定義では、相対近傍グラフは、 β = 2のβスケルトンの特殊なケースです 。2 つの定義は、β  ≤ 1 の場合は一致し、βの値が大きい場合は、円ベースのスケルトンはルーンベースのスケルトンの サブグラフになります。

円ベースの β スケルトンとルーンベースのβスケルトンの重要な違いの 1 つは、単一の直線上にない任意の点集合に対して、円ベースのβスケルトンが空のグラフになるほど十分に大きなβの値が常に存在することです。対照的に、点pとqのペアが、他のすべての点rに対して2 つの角度pqrとqprのいずれかが鈍角であるという特性を持つ場合、ルーンベースのβスケルトンには、βがどんなに大きくても、辺pq が含まれます。

βスケルトンは、Kirkpatrick と Radke (1985) によって、Edelsbrunner、Kirkpatrick、Seidel (1983) のアルファ形状のスケール不変変形として初めて定義されました。「 βスケルトン」という名前は、ある意味では、βスケルトンが、位相スケルトンが2 次元領域の形状を記述するのと同じ方法で、点の集合の形状を記述するという事実を反映しています。β スケルトンを他の空領域によって定義されるグラフに一般化するいくつかの方法も検討されています。^{[1] [2]}

β が0 から ∞ まで連続的に変化する場合は、円ベースのβスケルトンは、完全グラフから空グラフまで延びるグラフのシーケンスを形成します。 β = 1 の特別なケースは、ユークリッド最小全域木を含むことで知られるガブリエル グラフ につながります。したがって、β ≤ 1 の場合は常に、 βスケルトンにはガブリエル グラフと最小全域木も含まれます 。

任意の定数βに対して、コッホの雪片を平らにしたようなフラクタル構造を使用して、単位正方形内の任意の長さのパスであるβスケルトンを持つ点集合のシーケンスを定義できます。したがって、密接に関連しているドロネー三角形分割とは異なり、βスケルトンは無制限の伸縮係数を持ち、幾何学的スパナではありません。^[3]

領域Rpqにおけるrのメンバーシップについて各トリプルp、q、rを^{テストする}単純なアルゴリズムは、時間_O ( n3 )で任意のn点の集合のβスケルトンを構築できます。

β  ≥ 1の場合、 βスケルトン（どちらの定義でも）はガブリエルグラフのサブグラフであり、ガブリエルグラフはドロネー三角形分割のサブグラフです。pq がβスケルトンのエッジではないドロネー三角形分割のエッジである場合、大きな角度prq を形成する点r は、ドロネー三角形分割でpとqと三角形を形成する最大 2 つの点のうちの 1 つとして見つけることができます。したがって、これらのβの値に対して、ドロネー三角形分割を計算し、このテストを使用してエッジをフィルター処理することにより、 n点のセットの円ベースのβスケルトンをO( n  log  n ) の時間で構築できます。^[2]

β < 1の場合 、Hurtado、Liotta、Meijer (2003) の別のアルゴリズムを使用すると、βスケルトンを O( n ² ) の時間で構築できます。1 未満の任意の固定値βに対して、一般的な位置 (正多角形の小さな摂動) に、 βスケルトンが2 乗個の辺を持つ密なグラフである点集合が存在するため、これより悪いケースの時間境界は不可能です。同じ 2 乗の時間境界で、 βスペクトル全体( β を変化させることによって形成される円ベースのβスケルトンのシーケンス) も計算できます。

円ベースのβスケルトンは、物体の境界上のサンプルポイントのセットが与えられた場合に、画像分析で2次元物体の形状を再構築するために使用できます（ドットを接続するパズルの計算形式であり、ドットを接続する順序は、パズルの一部として与えられるのではなく、アルゴリズムによって推測される必要があります）。一般に、これにはパラメーターβの値を選択する必要がありますが、サンプルが表面の局所的な曲率に対して十分な密度で生成されている限り、 β  = 1.7 を選択すると、滑らかな表面の境界全体が正しく再構築され、境界に属さないエッジは生成されないことが証明されています。^{[4]ただし、実験では、地理情報システムで道路}の中心線を示すポイントのセットから道路地図を再構築するには、より低い値、β  = 1.2 の方が効果的でした。^[5] βスケルトン法の3次元表面再構成への一般化については、日吉（2007）を参照。

円ベースのβスケルトンは、点集合の最小重み三角形分割のサブグラフを見つけるために使用されてきました。βの値が十分に大きい場合、すべてのβスケルトンのエッジが最小重み三角形分割に属することが保証されます。このようにして見つかったエッジがすべての入力ポイントで接続されたグラフを形成する場合、残りの最小重み三角形分割のエッジは動的計画法によって多項式時間で見つけることができます。ただし、一般に最小重み三角形分割問題はNP困難であり、この方法で見つかったエッジのサブセットは接続されていない可能性があります。^[6]

βスケルトンは、機械学習において幾何学的分類問題を解決するためにも応用されている^{[7]。また、}無線アドホックネットワークにおいては、相互に通信できる無線局のペアのサブセットを選択することで通信の複雑さを制御するメカニズムとして応用されている^{[8] 。}