擬似三角形

ユークリッド平面幾何学において、擬似三角形（擬似三角形）は、互いに接する任意の 3 つの凸集合の間にある平面の単連結部分集合である。擬似三角形分割（擬似三角形分割群）は、平面の領域を擬似三角形に分割したもので、尖った擬似三角形分割は、各頂点で入射辺がπ 未満の 角度に広がる擬似三角形分割である。

「擬似三角形」や「擬似三角測量」という言葉は、数学において以前からさまざまな意味で使われてきましたが^[1] 、ここで使用されている用語は、1993 年に Michel Pocchiola と Gert Vegter によって、平面上の凸状障害物間の可視関係と従接線の計算に関連して導入されました。尖頭擬似三角測量は、 Ileana Streinu (2000、2005)によって、大工の定規問題の解決法の一部として初めて検討されました。これは、平面上の任意の単純な多角形の経路を、一連の連続した動作によってまっすぐにできることの証明です。擬似三角測量は、移動物体間の衝突検出^[2]や、動的なグラフ描画および形状モーフィング^{[3]にも使用されています。尖頭擬似三角測量は}、剛性理論において最小限の剛性平面グラフの例として、^[4]アート ギャラリー定理に関連してガード配置の方法にも登場します。^[5]平面点集合の殻反マトロイドは尖った擬似三角形分割を生じますが、^[6]すべての尖った擬似三角形分割がこのように生じるわけではありません。

ここで議論されている資料の詳細な調査については、Rote、Santos、およびStreinu (2008) を参照してください。

(Pocchiola & Vegter 1996a, 1996b, 1996c) は当初、擬似三角形を、端点で接する 3 つの滑らかな凸曲線で囲まれた平面の単連結領域と定義しました。^[7]しかし、その後の研究では、より一般的には多角形と滑らかな曲線で囲まれた領域に適用され、3 つの頂点で 0 以外の角度を許容する、より広い定義に落ち着きました。この広い定義では、擬似三角形は、3 つの凸頂点を持つ平面の単連結領域です。これらの 3 つの頂点を結ぶ 3 つの境界曲線は凸でなければなりません。つまり、同じ境界曲線上の 2 つの点を結ぶ線分は、擬似三角形の境界上またはその外側に完全に存在する必要があります。したがって、擬似三角形は、これらの 3 つの曲線の凸包の間の領域であり、より一般的には、互いに接する 3 つの凸集合は、その間にある擬似三角形を形成します。

アルゴリズム アプリケーションの場合、多角形である擬似三角形の特性を明らかにすることは特に重要です。多角形では、頂点がπ 未満の内角にまたがる場合は凸、そうでない場合は凹です(特に、角度がちょうど π の場合は凹とみなします)。多角形の合計外角は 2π であり、凸角はそれぞれこの合計に π 未満の割合で寄与し、凹角はゼロまたは負の量に寄与するため、多角形には少なくとも 3 つの凸角が必要です。多角形擬似三角形は、ちょうど 3 つの凸頂点を持つ多角形です。特に、任意の三角形および任意の非凸四辺形は擬似三角形です。

任意の擬似三角形の凸包は三角形です。各凸頂点のペア間の擬似三角形の境界に沿った曲線は、三角形内にあるか、三角形の辺の 1 つと一致します。

擬似三角形分割は、平面の領域を擬似三角形に分割することです。平面の領域の三角形分割はすべて擬似三角形分割です。同じ領域の 2 つの三角形分割には、同じ数の辺と三角形が必要ですが、擬似三角形分割の場合はそうではありません。たとえば、領域自体がn頂点の多角形擬似三角形である場合、その擬似三角形分割には、1 つの擬似三角形とn個の辺しか含まれない場合があります。また、n − 2 個の擬似三角形と 2 n − 3 個の辺が含まれる場合もあります。

極小擬似三角形分割とは、 Tのどの部分グラフも平面の同じ凸領域を覆う擬似三角形分割ではない擬似三角形分割Tのことである。n頂点を持つ極小擬似三角形分割は少なくとも 2 n − 3 辺を持つ必要がある。ちょうど 2 n − 3 辺を持つ場合は尖った擬似三角形分割である必要があるが、3 n − O(1) 辺を持つ極小擬似三角形分割も存在する。^[8]

Agarwal ら (2002) は、移動する点または移動する多角形の擬似三角測量を維持するためのデータ構造について説明しています。彼らは、三角測量の代わりに擬似三角測量を使用すると、入力が移動しても比較的少ない組み合わせの変更でアルゴリズムがこれらの構造を維持できることを示し、これらの動的な擬似三角測量を使用して移動するオブジェクト間の衝突検出を実行します。

Gudmundsson ら (2004) は、最小の合計辺長を持つ点集合または多角形の擬似三角形分割を見つける問題を考慮し、この問題の近似アルゴリズムを提供しています。

尖った擬似三角形分割は、交差しない有限の線分の集合として定義できます。この集合では、各頂点で入射線分は最大で π の角度に広がり、この特性を維持しながら既存の任意の 2 つの頂点間に線分を追加することはできません。尖った擬似三角形分割が凸包の擬似三角形分割であることは容易にわかります。つまり、すべての凸包の辺は角度に広がる特性を維持しながら追加でき、すべての内部面は擬似三角形でなければなりません。そうでない場合は、面の 2 つの頂点間に 二重接線分を追加できます。

v個の頂点を持つ尖った擬似三角形分割には、ちょうど 2 v − 3 個の辺がなければなりません。^{[9]これは、}オイラー特性を含む単純な二重カウントの議論によって従います。外側の面以外の各面は、3 つの凸角を持つ擬似三角形であるため、擬似三角形分割では、隣接する辺の間に 3 f − 3 個の凸角がなければなりません。各辺は、2 つの角度に対する時計回りの辺であるため、合計 2 e個の角があり、そのうちv以外はすべて凸角です。したがって、 3 f − 3 = 2 e − vです。これをオイラー方程式f − e + v = 2 と組み合わせて、結果として生じる連立一次方程式を解くと、 e = 2 v − 3が得られます。同じ議論から、f = v − 1 (面の 1 つとして凸包を含む) であることもわかるため、擬似三角形にはちょうどv − 2 個の擬似三角形がなければなりません。

同様に、尖った擬似三角形分割の任意のk頂点部分グラフは、その頂点の尖った擬似三角形分割を形成するように完成できるため、部分グラフは最大で 2 k − 3 辺を持つ必要があります。したがって、尖った擬似三角形分割は、ラマングラフを定義する条件を満たします。つまり、尖った擬似三角形分割はちょうど 2 v − 3 辺を持ち、そのk頂点部分グラフは最大で 2 k − 3 辺を持ちます。ラマングラフ、つまり尖った擬似三角形分割は、2 次元の最小限の剛性グラフです。すべての平面ラマングラフは尖った擬似三角形分割として描くことができますが、平面ラマングラフのすべての平面描画が擬似三角形分割であるとは限りません。^[10]

尖った擬似三角形分割を見つける別の方法は、点集合をシェル化すること、つまり、すべての点が削除されるまで凸包の頂点を1つずつ削除することです。この方法で形成できる削除シーケンスのファミリは、点集合のシェル化反マトロイドであり、この削除プロセスによって形成された点集合のシーケンスの凸包のエッジの集合は擬似三角形分割を形成します。^[6]ただし、すべての尖った擬似三角形分割がこのように形成できるわけではありません。

Aichholzer ら (2004) は、 h 個の点が集合の凸包に属するn個の点の集合には、少なくともC _{h −2} ×3 ^{n − h 個の}異なる尖った擬似三角形分割が存在する必要があることを示した。ここで、C _{i は}i番目のカタラン数を表す。結果として、彼らは、尖った擬似三角形分割が最も少ない点集合が凸多角形の頂点集合であることを示した。Aichholzer ら (2006) は、多数の尖った擬似三角形分割を持つ点集合を調査した。計算幾何学の研究者らは、擬似三角形分割ごとに短時間で点集合のすべての尖った擬似三角形分割をリストするアルゴリズムも提供した。^[11]

• 三角筋曲線
• 円形三角形