点集合三角形分割が三角形分割であるかどうかをチェック

Question

私はDelaunay triangulation（宿題ではない）を学習していました。次の問題について考えました。平面上に点群S（基数がn）と三角形T（基数がn-2である必要があります） - 三角形がTに設定されているかどうかを判断する方法は、Delaunay三角形分割DT(S)ですか？

最初の問題は、Delaunayの三角測量がユニークではないため、再度設定した点のために再構築し、設定された三角形と比較することで答えが得られないことです。さらに、最適なDelaunay三角形分割アルゴリズムは実装するのが難しいです（しかし、CGALのようなライブラリを使っても問題ありませんでした）。

三角形が三角形分割（必ずしもDelaunayではない）であるかどうかを確認する方法を知っているとします。次に、Delanuay三角測量の定義を使用する必要があります。三角形の中のすべての三角形tに対して、の点は、厳密には、円の内側のtにありません。これは、以下の方法につながります。

1. 些細なアプローチ。 Tを反復し、円周を計算して、Sを繰り返して、点が円周の内側にあるかどうかを確認します。しかし、これには時間がかかりますが、これはあまり最適ではありません。
2. エンチャンテッドアプローチ。再び、Tを繰り返して、円周を計算します。円の内側に点sがある場合は、円周の中心までの距離が半径よりも小さいことを意味します。 S以上の最近接検索構造を使用して、アルゴリズムを高速化します。例えば、単純なkd-tree構造は、平均でO(n log n)アルゴリズム、そして最悪の場合にはO(n sqrt(n))アルゴリズムにつながります。
3. 誰かがもっと簡単なアイデアを持っていますか？

次に、Tが三角測量であるかどうかをチェックする問題に戻りましょう。 Sの等価と三角形の頂点のセットのような単純な前提条件は、O(n log n)より速く実行することはできません。残っているもの - Tの2つの三角形がすべて共通の面に交差するか、まったく交差しないかを確認する。

1. ここでも、交差点をチェックし、TオーバーTと再びを反復処理することによってこれを行うことができますが、これはO(n^2)アルゴリズムです。
2. 三角形t1とt2が何を意味するのかを考えてみましょう。それらのエッジが交差する場合、または1つの三角形が完全に別の三角形にある場合、交差します。すべての辺を交差する問題は、Bentley-Ottmann algorithmを使用してO(n log n)の時間で解くことができます（最悪の場合はO((n + k) log n)です。ここで、kが最初の交差点を見つけた時点でアルゴリズムを停止できます）。また、ある三角形が完全に別の三角形を含む場合は認識しませんでしたが、Bentley-Ottmannアルゴリズムを修正して、セグメントの代わりに掃引線を横切る三角形を維持することができると信じており、私たちはO(n log n)アルゴリズムを生成します。しかし、実装するのは本当に複雑です。
3. 私は反復的なアルゴリズムについて考えました。交差していない（または辺でしか交差しない）三角形の構造を維持しようとします（kd-treeと非常に似ているはずです）。次に、次の三角形tを追加しようとします。tの頂点のいずれかがすでに三角形の1つにあるかどうかを最初に確認してから、交差点を取得します。それ以外の場合は、tを構造体に追加します。しかし、O(log n)またはO(sqrt(n))の検索に時間を費やしてクエリを追加する必要がある場合は、この構造体の高さのバランスをとる必要があります。これはkd木でも難しいです。

誰もがこの問題の簡単な解決法を知っていますか？

Answer 1

Delaunay補助定理があります。「Sの三角測量KのすべてのエッジがローカルDelaunayなら、KはSのDelaunay三角測量です。多分このことは、KがS.Dunnoの三角測量であることが確かであるあなたの質問のパラグラフ1からの状況で、このアプローチの計算上の複雑さを助けることができます。