輪読・計算幾何学 第3章　多角形の三角形分割 徳山研究室　M1 鈴木　晶子.

Presentation on theme: "輪読・計算幾何学 第3章　多角形の三角形分割 徳山研究室　M1 鈴木　晶子."— Presentation transcript:

1 輪読・計算幾何学 第3章　多角形の三角形分割 徳山研究室　M1 鈴木　晶子

2 発表の内容 美術館問題 三角形分割 単調な部分多角形への分割 単調な多角形の三角形分割

3 美術館問題 美術館に監視カメラを設置 カメラの台数はできるだけ少なく 美術館のどの部分も、少なくとも1台のカメラから見えるように
与えられた美術館を監視するのに必要なカメラの台数は? カメラはどこに配置すべき?

4 問題のモデル化 美術館→平面の多角形領域 単純な多角形(single polygon) 自己交差しない閉じた多角形チェインで囲まれた領域
多角形領域を三角形（監視が簡単な断片）に分割 →監視に必要なカメラ台数の上界を求める 単純な多角形 単純な多角形ではないもの

5 三角形分割

6 三角形分割 Pをn頂点の単純な多角形とする。 多角形Pの三角形分割 交差しない対角線の極大集合によって、多角形を三角形に分割したもの
対角線：Pの2頂点をPの内部だけを通って結ぶ開線分

7 定理3.1 どんな単純な多角形も三角形分割が可能である。 n頂点の単純多角形の任意の三角形分割は正確に n-2個の三角形からなる。 [証明]
n>3とし、全てのm<nに対して定理が成り立つと仮定する。 このとき、n頂点の多角形Pに対角線が引けることを示す。

8 定理3.1の証明 Pの最も左の頂点をvとする。 Pの境界上で、vに隣接する2頂点をu, wとする。
　　 がPの外部を通る場合は、u,v,wによって定義される三角形の内部、または対角線　　上に頂点が1個以上ある。 これらの頂点のうち、　　から最も遠いものをv’とする。 u u v v v’ w w

9 定理3.1の証明 vとv’を結ぶ線分はPの辺と交差することはない。 もし がPの辺と交差するとすれば、 と交差するPの辺は
u,v,wによって定義される三角形の内部に 端点をもち、さらにその点は 　　から最も遠いところになければならない。 　“　　 から最も遠い頂点”というv’の定義に矛盾 したがって、　　はPの辺と交差しない、つまり対角線である。 対角線は必ず存在する。 u v v’ w

10 P2 P P1 Pを2つの単純な多角形P1とP2に分割する。 P1の頂点数 : m1, P2の頂点数 : m2 m1とm2はnより小さくなければならない。 したがって帰納法の仮定より、 P1とP2は三角形分割可能。 Pも三角形分割可能 ここで、 m1 + m2 =n+2 また帰納法の仮定より、Pi の任意の三角形分割はmi-2個の三角形からなる。 したがって、Pの三角形分割は (m1 -2)+(m2 -2)=n-2個の三角形からなる。（証明終）

11 監視に必要なカメラの台数は? n頂点の単純多角形Pは、n-2個の三角形に分割可能 各三角形の内部に1台ずつカメラを配置
カメラを多角形の頂点に配置 1台のカメラで複数の 三角形を監視可能 定理3.2（美術館定理） n頂点の単純多角形に対して、多角形内のすべての 点が少なくとも1台のカメラから見えるようにするのに、 　　　台のカメラが必要になることがあり、またその台数で常に十分である。

12 カメラ配置のアイデア 三角形分割された多角形の3-彩色 どの三角形も赤、青、黄の頂点を1つずつもつ 3色のうち1色を選び、その色が
多角形の各頂点には赤、青、黄色のいずれか1色が割り当てられている 辺や対角線によって結ばれたどの2頂点も異なる色をもつ どの三角形も赤、青、黄の頂点を1つずつもつ 3色のうち1色を選び、その色が 割り当てられている頂点にカメラ を設置すると、　　　台のカメラで 全ての三角形を監視可能 3-彩色は必ず存在する?

13 三角形分割された多角形の3-彩色 Tp : Pの三角形分割 G(Tp) : Tpの双対グラフ Tpの全ての三角形に対して1つの節点をもつ
t(ν)とt(μ)が対角線を共有するとき、対応する2つの節点νとμの間にグラフの枝を引く どの対角線もPを2分する ↓ G(Tp)は木である

14 3-彩色の方法 グラフ探索法（深さ優先探索など）を用いる 節点を訪れたときに、対応する三角形の頂点に彩色する
新しく節点νを訪れたとき、三角形の3つの頂点のうち2つは既に色がつけられている ↓ 残る1点に色をつける グラフGは木なので、νに隣接 している他の頂点はまだ訪問 されていない 3-彩色は必ず存在する

15 単調な部分多角形への分割

16 三角形分割のアイデア 凸でない多角形Pを三角形分割する方法 Pを単調な多角形に分割する 分割された多角形を三角形分割する y単調な多角形
y軸に垂直などんな直線lに対しても、lと多角形との交差部分が連結であるようなもの lと多角形との交差部分は線分、1点、空のいずれか y軸 y軸 l l

17 単調な多角形を求めるアイデア y単調な多角形の特徴
最も上の頂点から最も下の頂点まで、左（あるいは右）の境界をたどるとき、常に下向きか水平に進んでいく 多角形の最も上の頂点から最も下の頂点へたどっていくとき、下向きから上向きに変化する頂点（変曲点）を取り除けばよい 変曲点から対角線を引くことにより取り除く start y単調な多角形を得るためには... goal

18 多角形の頂点の分類 出発点(start vertex) 分離点(split vertex) 最終点(end vertex)
隣接頂点が両方とも下にあり、 内角がπより小さい 分離点(split vertex) 隣接頂点が両方とも下にあり、 内角がπより大きい 最終点(end vertex) 隣接頂点が両方とも上にあり、 内角がπより小さい 統合点(merge vertex) 隣接頂点が両方とも上にあり、 内角がπより大きい 普通の頂点(regular vertex) それ以外

19 y単調な多角形の性質 補題3.4 分離点も統合点ももたない多角形はy単調である。 [証明]
「Pがy単調でないとき、Pは分離点か統合点をもつ」ことを示す。 Pはy単調でないので、Pと交差する部分が2つ以上の成分に 分かれるような水平線lが存在する。 このとき最も左の成分の左端点をp, 右端点をqとする。 qから出発して、Pの内部を左に見ながら Pの境界をたどると、ある点rで境界はlと 再び交差するはずである。 P p r l q

20 補題3.4の証明 p≠rのとき 分離点 q からrまでの道のりで最も高いところにある頂点は分離点でなければならない。 P p=rのとき
qから出発して、Pの内部を右に見ながらPの境界をたどる。このとき境界がlと交差する点をr’とする。 もしr’=pなら、Pの境界はlと2回しか交差しないことになるため、r’≠pである。 このときqからr’までの道のりで最も低いところにある頂点は、統合点でなければならない。 分離点 P p r l q P q r’ l p=r 統合点

21 アルゴリズムのアイデア 平面走査法を用いて、分離点と統合点を取り除く 仮想的な走査線lを上から下へと動かしていく。
lが分離点viに到達したとき、lからの距離が最小でviより上にある頂点と、viとを結ぶ。 l helper(ej) ej ek ejのヘルパー 分離点vi

22 アルゴリズムのアイデア 平面走査法を用いて、分離点と統合点を取り除く
lが統合点viに到達したとき、lからの距離が最小でviより下にある頂点と、viとを結ぶ。 helper(ej) : 移動前 統合点vi viの次に ejのヘルパーになる点 l ej ek helper(ej) : 移動後

23 単調な多角形に分割するアルゴリズム MAKEMONOTONE(P) 入力 2重連結辺リストの形で蓄えられた単純多角形P 出力
2重連結辺リストDに蓄えられた、Pの単調な部分多角形への分割 用意しておくもの y座標値を優先順位として用いた、Pの頂点に関するプライオリティキューQ 走査線と交差するPの辺（とそのヘルパー）を蓄えておく、2分探索木T（空に初期化する）

24 アルゴリズムの実行例 Q v5 v3 v4 v6 v7 v1 v9 v2 v8 v14 v10 v15 v12 v11 v13 l v5
T v4 e5 e4 e3 v6 e5 e6 e2 helper v5 v7 v1 v2 v9 e7 e1 e8 HANDLESTARTVERTEX(v5) e5をTに挿入し、 e5のヘルパーをv5とする。 v8 e9 e15 e14 v14 v10 e10 v15 e13 e11 v12 e12 v11 v13

25 アルゴリズムの実行例 Q v5 v3 v4 v6 v7 v1 v9 v2 v8 v14 v10 v15 v12 v11 v13 v5 v3
T v4 e3 v3 e5 e4 e3 l v6 e5 e6 e2 helper v5 v7 v1 →v4 v2 v9 e7 e1 e8 HANDLEMERGEVERTEX(v4) e5のヘルパーもe3のヘルパーも統合点ではないので、対角線は引かない。 lはe3と交差しなくなるのでTからを削除し、 e5のヘルパーをv4に変更する。 v8 e9 e15 e14 v14 v10 e10 v15 e13 e11 v12 e12 v11 v13

26 アルゴリズムの実行例 Q v5 v3 v4 v6 v7 v1 v9 v2 v8 v14 v10 v15 v12 v11 v13 v5 v3
T v4 e5 e4 e3 l v6 e5 e6 e6 e2 helper v4 v6 v7 v1 v2 v9 e7 e1 e8 HANDLEREGULARVERTEX(v6) e5のヘルパー(v4)が統合点なので、v6からv4へ対角線をひく。 lはe5と交差しなくなりe6と交差するようになるので、 e5をTから削除し、代わりにe6を挿入する。 v8 e9 e15 e14 v14 v10 e10 v15 e13 e11 v12 e12 v11 v13

27 アルゴリズムの実行例 Q v5 v3 v4 v6 v7 v1 v9 v2 v8 v14 v10 v15 v12 v11 v13 v5 v3
T v4 e7 v2 e5 e4 e3 v6 e9 e6 e2 helper v9 v7 v1 →v8 v2 v9 e7 e1 e8 l HANDLEMERGEVERTEX(v8) e7のヘルパー(v2)が統合点なので、v8からv2へ対角線を引く。 lはe7と交差しなくなるのでTからを削除し、 e9のヘルパーをv8に変更する。 v8 e9 e15 e14 v14 v10 e10 v15 e13 e11 v12 e12 v11 v13

28 アルゴリズムの実行例 Q v5 v3 v4 v6 v7 v1 v9 v2 v8 v14 v10 v15 v12 v11 v13 v5 v3
T v4 e14 v14 e5 e4 e3 v6 e9 e6 e2 helper v8 v7 v1 →v14 v2 v9 e7 e1 e8 HANDLESPLITVERTEX(v14) v14とv8 （ e9のヘルパー）を結ぶ対角線を引く。 e9のヘルパーをv14に変更する。 e14をTに挿入し、そのヘルパーをv14とする。 v8 e9 e15 e14 v14 l v10 e10 v15 e13 e11 v12 e12 v11 v13

29 アルゴリズムの実行例 Q v5 v3 v4 v6 v7 v1 v9 v2 v8 v14 v10 v15 v12 v11 v13 v5 v3
T v4 e14 v14 e5 e4 e3 v6 e10 e6 e2 helper v10 v7 v1 v2 v9 e7 e1 e8 HANDLEENDVERTEX(v15) e14のヘルパーは統合点ではないので、対角線は引かない。 e14をTから削除する。 v8 e9 e15 e14 v14 v10 l e10 v15 e13 e11 v12 e12 v11 v13

30 アルゴリズムの実行例 Q v5 v3 v4 v6 v7 v1 v9 v2 v8 v14 v10 v15 v12 v11 v13 v5 v3
T v4 e12 v12 e5 e4 e3 v6 e10 e6 e2 helper v10 v7 v1 →v12 v2 v9 e7 e1 e8 HANDLESPLITVERTEX(v12) v12とv10 （ e10のヘルパー）を結ぶ対角線を引く。 e10のヘルパーをv12に変更する。 e12をTに挿入し、そのヘルパーをv12とする。 v8 e9 e15 e14 v14 v10 e10 l v15 e13 e11 v12 e12 v11 v13

31 補題3.5 アルゴリズムMAKEMONOTONEによって加えられる対角線の集合は、互いに交差することなくPを単調な多角形に分割する。 [証明] Pが分割されてできる部分多角形は分離点も統合点も含まないことは明らか。 したがって、線分が挿入された時にその線分が Pの辺と交差しない 以前に挿入された線分と交差しない ことを示す。

32 vm 分離点viに到達した時に、Pに加えられる線分　　　 を考える。 viのすぐ左にある辺をej, すぐ右にある辺をekとする。 vi, vmを通る2本の水平線分とej, ekを境界とする四角形をQとする。 Q ek ej vi 四角形Qの中に、Pの頂点は存在しない。 もし存在すれば、その頂点が辺ejのヘルパーとなり、 vmがejのヘルパーでなくなってしまう。 次に、　　と交差するPの辺が存在すると仮定する。 この辺は、Qの中に端点を持つことはできないため、 viとejを結ぶ水平線分か、 vmとejを結ぶ水平線分と交差するはずである。 しかしvi, vmのどちらに対しても、それらの頂点のすぐ左にある辺はejなので、　　　と交差する辺は存在しない。

33 vm Q ek ej vi 以前に付け加えられた対角線との交差について考える。 Qの内部にPの頂点は存在しない。 また、以前付け加えられた対角線の両端点は、viよりも上になければならない。 したがって、　　　と交差することはない。 viが統合点、最終点、普通の頂点の場合にも同様の性質が成り立つ。

34 アルゴリズムの実行時間 プライオリティキューQの構成→O(n)時間 2分探索木Tの初期化→O(1)時間
1つの頂点に到達したときに行われる処理 Qに関する操作(1回)→O(logn)時間 Tに関する質問(高々1回)、挿入、削除(1回) →O(logn)時間 Dへの対角線の挿入(高々2本)→O(1)時間 1つのイベントに対してO(logn)時間 n個の頂点に対して処理を行うので、全体での実行時間はO(nlogn)

35 定理3.6 記憶領域O(n)のアルゴリズムにより、n頂点の単純多角形をO(nlogn)の時間でy単調な多角形に分割することができる。

36 単調な多角形の三角形分割

37 アルゴリズムの概要 y座標値の降順に頂点を処理する。
既に出会ったが、まだ対角線が引かれていない頂点を蓄えておくための、スタックSを用意しておく。 1つの頂点を処理するとき、その頂点からスタック内の頂点に向けてできるだけ多数の対角線を引く。 S v5 v4 v3 v2 v1 v1 v2 v3 v4 v5 v6

38 アルゴリズムのポイント アルゴリズムの実行中に常に成り立つ性質
まだ三角形分割しなければならないPの部分で、これまでに調べた最後の頂点より上にある部分 Pの一つの辺 鈍角の頂点からなる多角形チェイン が境界となっている まだ三角形分割 されていない部分

39 三角形分割アルゴリズム TRIANGULATEMONOTONEPOLYGON(P) 入力
2重連結辺リストDの形で蓄えられた、厳密にy単調な多角形P 出力 2重連結辺リストDの形で蓄えられた、Pの三角形分割 y座標値の降順にソートされたPの左側のチェイン上の頂点列と、右側のチェイン上の頂点列を一つの系列に統合する。 ソート列をu1,…,unとする。

40 三角形分割アルゴリズム u1とu2をスタックSにプッシュする。 u3~un-1の頂点ujは、以下のように処理する。
ujとSの一番上の頂点が異なるチェイン上にある場合 →Sからすべての頂点をポップし、 ujとポップされたそれぞれの頂点とを結ぶ。 S S uj-1 uj-2 uj uj-1 uj-2 uj-1 … uj

41 三角形分割アルゴリズム u3~un-1の頂点ujは、以下のように処理する。 ujとSの一番上の頂点が同じチェイン上にある場合
→Sから一つずつ頂点をポップし、 ujからの対角線がPの内部にある限り、対角線を引く。 最初と最後の頂点を除いて、unからすタック上の全ての頂点への対角線を加える。 S uj-1 uj-2 uk uk-1 S uj uk uk … uj-1 uj

42 アルゴリズムの計算時間 u1とu2をスタックSにプッシュする。→O(1)時間 u3~un-1の処理(n-3回の繰り返し処理)
スタックへのプッシュの回数 →1頂点の処理につき高々2回 スタックからのポップの回数 →プッシュの回数以下 ⇒O(n)時間 定理3.7 n頂点の厳密にy単調な多角形は、線形時間で三角形分割できる。

43 まとめ 多角形の監視 単純多角形をy単調な多角形に分割 y単調な多角形を三角形分割 3-彩色によりカメラを配置 定理3.3
Pをn頂点の単純多角形とする。 P内のどの点も少なくとも1台のカメラから見えるようにPの中に　　　台のカメラを配置する方法をO(nlogn)時間で求めることができる。