INTRODUCTION TO ALGORITHMS

Transcription

1 関根渓 ( 情報知識ネットワーク研究室 B4) INTRODUCTION TO ALGORITHMS 33. Computational Geometry 33.3 Finding the convex hull 33.4 Finding the closest pair of points

2 CONTENTS 33.3 凸包の構成 (Finding the convex hull) 33.4 最近点対の発見 (Finding the pair of closest points)

3 CONTENTS 33.3 凸包の構成 (Finding the convex hull) 凸包 (convex hull) とは? 凸包を計算するアルゴリズム

4 凸包 (convex hull) とは? 点集合 Q の凸包とは Q の各点がその境界上にあるような最小の凸多角形 P のこと Q の凸包を CH(Q) と表現 0 Q={,,p2,,2} 直感的には 集合の各点を板から飛び出ている釘とし それら全ての釘を取り囲むきつい輪ゴムが作る形状が凸包 2 1 p9 p8 p6 p5 p7 p4 p2 点集合 Q とその凸包 CH(Q)

5 凸包 (convex hull) とは? 凸包ではない例 例 1: 境界線外に点が存在 0 例 2: 凸多角形ではない p9 p7 p8 p6 p5 p4 p2 2 Q={,,p2,,2} 1 p9 p7 p8 p6 p5 p4 p2

6 CONTENTS 33.3 凸包の構成 (Finding the convex hull) 凸包 (convex hull) とは? 凸包を計算するアルゴリズム

7 凸包を計算する様々なアルゴリズムの紹介 1. 逐次添加法 (incremental method) 2. 分割統治法 (divided-and-conquer method) 3. 枝刈り探索法 (prune-and-search method) 4. Graham スキャン (Graham s scan) 5. Jarvis の行進法 (Jarvis s march)

8 逐次添加法 (incremental method) 点を左から右の順にソートし ソート列 <,,,pn> 求める. i 番目の段階で, 左から i-1 個目の凸包 CH({,,,pi}) を作る. 実行時間は O(nlogn) である. イメージとしては i=2 CH({,,,pi}) の頂点がスタックに積まれていく凸包を構成する点は最小で 3 点 ( 三角形 ) なので, 最初は,p2, が PUSH される Q={,,p2,,2} p2 p2 p4 p5 p6 p7 stack

9 逐次添加法 (incremental method) 点を左から右の順にソートし ソート列 <,,,pn> 求める. i 番目の段階で, 左からi-1 個目の凸包 CH({,,,pi}) を作る. 実行時間はO(nlogn) である. イメージとしては i=3 と CH({,,,p2}) の接線を求め, CH({,,,}) の辺とし, 辺に挟まれる境界線を取り除く この手続きをスタックの命令で表すと, 水平軸方向において, 接点と参照点の間にある点全てをスタックから POP し, 参照点を PUSH する, ということになる Q={,,p2,,2} p2 p2 p4 p5 p6 p7 stack

10 逐次添加法 (incremental method) 点を左から右の順にソートし ソート列 <,,,pn> 求める. i 番目の段階で, 左から i-1 個目の凸包 CH({,,,pi}) を作る. 実行時間は O(nlogn) である. イメージとしては i=3 が PUSH される Q={,,p2,,2} p2 p2 p4 p5 p6 p7 stack

11 逐次添加法 (incremental method) 点を左から右の順にソートし ソート列 <,,,pn> 求める. i 番目の段階で, 左から i-1 個目の凸包 CH({,,,pi}) を作る. 実行時間は O(nlogn) である. イメージとしては i=3 p4 と CH({,,,}) の接線を求め, CH({,,,p4}) の辺とし, 辺に挟まれる境界線を取り除く Q={,,p2,,2} p2 p2 p4 p5 p6 p7 stack

12 1. 逐次添加法 (incremental method) 点を左から右の順にソートし ソート列 <,,,pn> 求める. i 番目の段階で, 左から i-1 個目の凸包 CH({,,,pi}) を作る. 実行時間は O(nlogn) である. イメージとしては i=4 p4 が PUSH される Q={,,p2,,2} p2 p4 p2 p4 p5 p6 p7 stack

13 1. 逐次添加法 (incremental method) 点を左から右の順にソートし ソート列 <,,,pn> 求める. i 番目の段階で, 左から i-1 個目の凸包 CH({,,,pi}) を作る. 実行時間は O(nlogn) である. イメージとしては i=5 p5 と CH({,,,p4}) の接線を求め, CH({,,,p5}) の辺とし, 辺に挟まれる境界線を取り除く Q={,,p2,,2} p2 p4 p2 p4 p5 p6 p7 stack

14 逐次添加法 (incremental method) 点を左から右の順にソートし ソート列 <,,,pn> 求める. i 番目の段階で, 左から i-1 個目の凸包 CH({,,,pi}) を作る. 実行時間は O(nlogn) である. イメージとしては i=5 境界線上の点である と p4 が POP され, p5 が PUSH される Q={,,p2,,2} p2 p5 p2 p4 p5 p7 p6 stack

15 逐次添加法 (incremental method) 点を左から右の順にソートし ソート列 <,,,pn> 求める. i 番目の段階で, 左から i-1 個目の凸包 CH({,,,pi}) を作る. 実行時間は O(nlogn) である. イメージとしては i=6 p6 と CH({,,,p5}) の接線を求め, CH({,,,p6}) の辺とし, 辺に挟まれる境界線を取り除く Q={,,p2,,2} p2 p5 p2 p4 p5 p7 p6 stack

16 逐次添加法 (incremental method) 点を左から右の順にソートし ソート列 <,,,pn> 求める. i 番目の段階で, 左から i-1 個目の凸包 CH({,,,pi}) を作る. 実行時間は O(nlogn) である. イメージとしては i=6 境界線上の点である p5 が POP され, p6 が PUSH される Q={,,p2,,2} p2 p6 p2 p4 p5 p7 p6 stack

17 逐次添加法 (incremental method) 点を左から右の順にソートし ソート列 <,,,pn> 求める. i 番目の段階で, 左から i-1 個目の凸包 CH({,,,pi}) を作る. 実行時間は O(nlogn) である. イメージとしては i=7 p7 と CH({,,,p6}) の接線を求め, CH({,,,p7}) の辺とし, 辺に挟まれる境界線を取り除く Q={,,p2,,2} p2 p6 p2 p4 p5 p7 p6 stack

18 逐次添加法 (incremental method) 点を左から右の順にソートし ソート列 <,,,pn> 求める. i 番目の段階で, 左から i-1 個目の凸包 CH({,,,pi}) を作る. 実行時間は O(nlogn) である. イメージとしては i=7 p7 が PUSH されて 処理が終了 Q={,,p2,,2} p2 p7 p6 p2 p4 p5 p6 p7 stack

19 逐次添加法 (incremental method) 点を左から右の順にソートし ソート列 <,,,pn> 求める. i 番目の段階で, 左から i-1 個目の凸包 CH({,,,pi}) を作る. 実行時間は O(nlogn) である. イメージとしては Q={,,p2,,2} p2 i=7 大きな問題点が発生!! p7 が PUSH されて 処理が終了 p7 p6 p2 p4 p5 p6 p7 stack

20 逐次添加法 (incremental method) その問題点とは? スタックに積まれている点は, それが凸包の頂点であるということしか表していない つまりどの点とどの点を結べば凸包が作れるのかわからない そこで 解決法として以下のような技法が挙げられる p2 赤線 : 上部凸包黄線 : 下部凸包 線分 p7 を境界線として点集合を二つの部分集合に分割, それぞれの部分集合に対する凸包 ( 上部凸包 下部凸包 ) を逐次添加法で求める 線分 p7 p4 p7 上部凸包の頂点を含むスタックを S1 下部凸包の頂点を含むスタックを S2 とすると, p5 p6 これらは水平座標について左から右の順に頂点を含んでいるため,S2 を逆順にソートしたものを S1 と組み合わせて出力すれば, 凸包の頂点が時計回りに出力されることとなる

21 逐次添加法 (incremental method) 接点の選び方 接点はその時凸包の頂点となっている点のうちのどれかであるスタックに積まれている順にそれが接点であるかを調べていく i=5 例 : 3 p2 1 p4 接点ではないのでスタックから POP 2 接点ではないのでスタックから POP p4 p5 p6 p7 3 4 p2 stack 接点なのでそのまま 接点なのでそのまま 一度スタックに PUSH された点が POP されるのは高々 1 回であるから, アルゴリズム全体の POP の回数は n-3 回未満である つまり凸包の更新は全体で n-3(pop 回数 )+2n( 接点の選択 )=O(n) 時間しかかからない

22 逐次添加法 (incremental method) 計算量の吟味凸包の更新には全体で O(n) ( 前項より ) 左から右の順に点をソートするのに O(nlogn) ( マージソート等 ) PUSH 命令には O(n) したがって, 逐次添加法の計算量はソーティングに依存することとなり, 全体で O(nlogn) となる 以上から, Exercise 逐次添加法を用いて n 点の凸包を O(nlogn) 時間で計算する方法を示せ. は示された.

23 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する. イメージ的には

24 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する. イメージ的には 1 n 点の集合を 2 つの部分集合に分割

25 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する. イメージ的には 2 1

26 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

27 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

28 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

29 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する. 2 つの凸包 ( または直線 ) の上部接線を求め それらを辺として一つに統合する 3 2 1

30 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する. 2 つの凸包 ( または直線 ) の上部接線を求め それらを辺として一つに統合する 3 2 1

31 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

32 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

33 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

34 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

35 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

36 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

37 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

38 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

39 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

40 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

41 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

42 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

43 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

44 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

45 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

46 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

47 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

48 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

49 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

50 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

51 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

52 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する

53 分割統治法 (divide-and-conquer method) Θ(n) 時間で n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の凸包を再帰的に計算し, 巧妙な方法を用いてこれらの凸包を O(n) 時間で統合する.

54 分割統治法 (divide-and-conquer method) 上部接線の求め方 q4 r3 左の凸包の最右点 q3 右の凸包の最左点 r5 を線で結ぶ Us: 線分 (q3,r5) とすると r5 r4 Us は r5 において接線である q3 において接線ではない q3 r6 Us: 線分 (q4,r5) とする r2 q5 q2 r1 q1

55 分割統治法 (divide-and-conquer method) 上部接線の求め方 q4 r3 Us: 線分 (q4,r5) とすると Us は q4 において接線である r5 において接線ではない r4 Us: 線分 (q4,r4) とする r5 q3 r6 r2 q5 q2 r1 q1

56 分割統治法 (divide-and-conquer method) 上部接線の求め方 q4 r3 Us: 線分 (q4,r4) とすると Us は q4 において接線である r5 において接線ではない r4 Us: 線分 (q4,r3) とする r5 q3 r6 r2 q5 q2 r1 q1

57 分割統治法 (divide-and-conquer method) 上部接線の求め方 q4 r3 Us: 線分 (q4,r3) とすると Us は q4 において接線である ( 傾き Us> 直線 q4q5) r3 において接線である ( 傾き Us 直線 >r3r2) r4 よって q4r3 は上部接線であり, 凸包の辺 r5 q3 r6 r2 q5 q2 r1 q1

58 分割統治法 (divide-and-conquer method) 下部接線の求め方 上部接線を求めた方法で 下方向に頂点を辿ることで求まる q4 r3 r5 r4 q3 r6 r2 q5 q2 r1 q1

59 枝刈り探索法 (prune-and-search method) 9.3 節の最悪線形時間の中央値発見アルゴリズムとよく似ている. 凸包の上側部分 ( 上部チェイン ) だけが残るまで残りの点のうちの一定割合を繰り返し捨てることによって凸包の上側部分を求める. 次に, 同じ方法で下部チェインを求める. 凸包が h 個の頂点を含んでいるとき O(nlogh) 時間しかかからない. Q={,,p2,,2} 0 赤線 : 上部チェイン黄線 : 下部チェイン 2 1 p9 p8 p6 p5 p7 p4 p2 点集合 Q とその凸包 CH(Q)

60 凸包を計算するということ 計算幾何問題には凸包の計算から始めるものが多い例 : 最遠点対 (farthest pair problem) 平面上の n 点集合が与えられたときの互いの距離が最大となるような2 点のこと これら2 点は必ず凸包の頂点となる ( 練習問題 より ) n 点集合

61 凸包を計算するということ 計算幾何問題には凸包の計算から始めるものが多い例 : 最遠点対 (farthest pair problem) 平面上の n 点集合が与えられたときの互いの距離が最大となるような2 点のこと これら2 点は必ず凸包の頂点となる ( 練習問題 より ) n 点集合 最遠点対 証明は省くが, 凸 n 角形の最遠点対は O(n) 時間で計算可能 n 個の入力点の凸包を O(nlogn) 時間で計算し, 求められた凸多角形の頂点の最遠点を求めれば, 任意の n 点集合の最遠点対を O(nlogn) 時間で計算できる

62 これから紹介するアルゴリズムについて Graham スキャン (Graham s scan) 実行時間 :O(nlogn) Jarvis の行進法 (Jarvis s march) 実行時間 :O(nh) ( ただし hは凸包の頂点数 ) Q の頂点のうちどれを凸包の頂点として持つか どれを捨てるかを判定する 凸包の頂点を反時計回りの順に出力 ある参照点に関する偏角順に点を処理する 回転走査 と呼ばれる技法を用いる

63 回転走査 ある参照点についての偏角の順に点を処理する 1 参照点 p

64 回転走査 ある参照点についての偏角の順に点を処理する 2 参照点 p

65 回転走査 ある参照点についての偏角の順に点を処理する 3 参照点 p

66 回転走査 ある参照点についての偏角の順に点を処理する 4 参照点 p

67 回転走査 ある参照点についての偏角の順に点を処理する 5 参照点 p

68 回転走査 ある参照点についての偏角の順に点を処理する 6 参照点 p

69 回転走査 ある参照点についての偏角の順に点を処理する 7 参照点 p

70 Graham スキャン (Graham s scan) 候補点をスタック S で管理しながら凸包問題を解く 入力集合 Q の各点はいったんスタックに入れられ,CH(Q) の頂点でない点は最終的にはスタックから取り除かれる アルゴリズム終了の時点で, スタックはCH(Q) の頂点だけを, 境界面上での反時計回りの出現順に含む Graham s scan 終了時のスタック 入力集合 Q={,,p2,,2} p6 p7 p6 p7 p4 p5 p2 p2 stack

71 Graham スキャン (Graham s scan) 手続き GRAHAM-SCAN 入力 : 点集合 Q ただし Q 3 TOP(S): スタックSの一番上の点を返す関数 Line 1 NEXT-TO-TOP(S): スタックSの上から二番目の点を返す関数集合 Qのy 座標最小の点をとする複数あれば最左のものをとする アルゴリズム GRAHAM-SCAN(Q) 1 let p 0 be the point in Q with the minimum y-coordinate, or the leftmost such point in case of a tie 2 let <p 1, p 2,, p m > be the remaining points in Q, sorted by polar angle in counterclockwise order around p 0 (if more than one point has the same angle, remove all but the one that is farthest from p 0 ) 3 PUSH(p 0,S) 4 PUSH(p 1,S) 5 PUSH(p 2,S) 6 for i 3 to m 7 do while the angle formed by points NEXT-TO-TOP(S), TOP(S), and p i makes nonleft turn 8 do POP(S) 9 PUSH(p i, S) 10 return S

72 Graham スキャン (Graham s scan) 手続き GRAHAM-SCAN 入力 : 点集合 Q ただし Q 3 TOP(S): スタックSの一番上の点を返す関数 NEXT-TO-TOP(S): スタックSの上から二番目の点を返す関数ソートしたものを <,p2,.,pm> とする アルゴリズム Line 2 Q の残りの点を の周りの反時計回りの偏角順に 複数の点が同じ偏角をもつときは から最遠となるもの以外は取り除く GRAHAM-SCAN(Q) 1 let p 0 be the point in Q with the minimum y-coordinate, or the leftmost such point in case of a tie 2 let <p 1, p 2,, p m > be the remaining points in Q, sorted by polar angle in counterclockwise order around p 0 (if more than one point has the same angle, remove all but the one that is farthest from p 0 ) 3 PUSH(p 0,S) 4 PUSH(p 1,S) 5 PUSH(p 2,S) 6 for i 3 to m 7 do while the angle formed by points NEXT-TO-TOP(S), TOP(S), and p i makes nonleft turn 8 do POP(S) 9 PUSH(p i, S) 10 return S

73 Graham スキャン (Graham s scan) 手続き GRAHAM-SCAN 入力 : 点集合 Q ただし Q 3 TOP(S): スタックSの一番上の点を返す関数 NEXT-TO-TOP(S): スタックSの上から二番目の点を返す関数 アルゴリズム GRAHAM-SCAN(Q) 1 let p 0 be the point in Q with the minimum y-coordinate, or the leftmost such point in case of a tie 2 let <p 1, p 2,, p m > be the remaining points in Q, sorted by polar angle in counterclockwise order around p 0 (if more than one point has the same angle, remove all but the one that is farthest from p 0 ) 3 PUSH(p 0,S) 4 PUSH(p 1,S) 5 PUSH(p 2,S) 6 for i 3 to m Line 3-5,,p2 をスタックに PUSH 7 do while the angle formed by points NEXT-TO-TOP(S), TOP(S), and p i makes nonleft turn 8 do POP(S) 9 PUSH(p i, S) 10 return S

74 Graham スキャン (Graham s scan) 手続き GRAHAM-SCAN 入力 : 点集合 Q ただし Q 3 TOP(S): スタック S の一番上の点を返す関数 NEXT-TO-TOP(S): スタック S の上から二番目の点を返す関数 アルゴリズム GRAHAM-SCAN(Q) 1 let p 0 be the point in Q with the minimum y-coordinate, or the leftmost such point in case of a tie 2 let <p 1, p 2,, p m > be the remaining points in Q, sorted by polar angle in counterclockwise order around p 0 Line 6-9 for ループ部分列 <,p4,.,pm> の各点について一度ずつ繰り返す目的は, 点 piを処理した後, スタックSが底から先頭に向けて CH({,,,2}) の頂点を反時計周り の順に含むようにすること (if more than one point has the same angle, remove all but the one that is farthest from p 0 ) 3 PUSH(p 0,S) 4 PUSH(p 1,S) 5 PUSH(p 2,S) 6 for i 3 to m 7 do while the angle formed by points NEXT-TO-TOP(S), TOP(S), and p i makes nonleft turn 8 do POP(S) 9 PUSH(p i, S) 10 return S

75 Graham スキャン (Graham s scan) 手続き GRAHAM-SCAN 入力 : 点集合 Q ただし Q 3 TOP(S): スタック S の一番上の点を返す関数 NEXT-TO-TOP(S): スタック S の上から二番目の点を返す関数 アルゴリズム Line 7-8 while ループ凸包の頂点を形成しないことがわかったときに, そのような点をスタックから取り除く GRAHAM-SCAN(Q) 1 let p 0 be the point in Q with the minimum y-coordinate, 凸包を反時計回りに回るとき, 各頂点で左に曲がるはず or the leftmost such point in case of a tie 2 let <p 1, p 2,, p m > be the ループで左折しない点を見つけたら remaining points in Q,, その度に頂点をスタッ sorted by polar angle クから取り除く in counterclockwise order around p 0 (if more than one point has the same angle, remove all but the one that is farthest from p 0 ) 3 PUSH(p 0,S) 4 PUSH(p 1,S) 5 PUSH(p 2,S) 6 for i 3 to m 7 do while the angle formed by points NEXT-TO-TOP(S), TOP(S), and p i makes nonleft turn 8 do POP(S) 9 PUSH(p i, S) 10 return S

76 Graham スキャン (Graham s scan) 手続き GRAHAM-SCAN 入力 : 点集合 Q ただし Q 3 TOP(S): スタックSの一番上の点を返す関数 NEXT-TO-TOP(S): スタックSの上から二番目の点を返す関数 アルゴリズム GRAHAM-SCAN(Q) 1 let p 0 be the point in Q with the minimum y-coordinate, or the leftmost such point in case of a tie 2 let <p 1, p 2,, p m > be the remaining points in Q, sorted by polar angle in counterclockwise order around p 0 (if more than one point has the same angle, remove all but the one that is farthest from p 0 ) 3 PUSH(p 0,S) 4 PUSH(p 1,S) 5 PUSH(p 2,S) 6 for i 3 to m 7 do while the angle formed by points NEXT-TO-TOP(S), TOP(S), and p i makes nonleft turn 8 do POP(S) 9 PUSH(p i, S) 10 return S

77 Graham スキャン (Graham s scan) 動作例 入力集合 Q( 未ソート )

78 Graham スキャン (Graham s scan) 動作例 集合 Q に含まれる点のうち, y 座標の最も小さい点を とする

79 Graham スキャン (Graham s scan) 動作例 0 P0 に対する偏角の順に残りの点をソートする 1 p9 p8 p7 p6 p5 2 p4 p2

80 Graham スキャン (Graham s scan) 動作例 0,,p2 を S に PUSH 1 p9 p7 p6 p5 2 p8 p4 p2 p2 stack S

81 Graham スキャン (Graham s scan) 動作例 0 i=3 NEXT-TO-TOP(S)= TOP(S)=p2 pi= p2 は右回り p2 を POP 1 p9 p7 p6 p5 2 p8 p4 p2 p2 stack S

82 Graham スキャン (Graham s scan) 動作例 0 i=3 NEXT-TO-TOP(S)= TOP(S)=p2 pi= p2 は右回り p2 を POP 1 p9 p7 p6 p5 2 p8 p4 p2 stack S

83 Graham スキャン (Graham s scan) 動作例 0 i=3 NEXT-TO-TOP(S)= TOP(S)= pi= は左回り を PUSH 1 p9 p7 p6 p5 2 p8 p4 p2 stack S

84 Graham スキャン (Graham s scan) 動作例 0 i=3 NEXT-TO-TOP(S)= TOP(S)= pi= は左回り を PUSH 1 p9 p7 p6 p5 2 p8 p4 p2 stack S

85 Graham スキャン (Graham s scan) 動作例 0 i=4 NEXT-TO-TOP(S)= TOP(S)= pi=p4 p4 は左回り p4 を PUSH 1 p9 p7 p6 p5 2 p8 p4 p2 stack S

86 Graham スキャン (Graham s scan) 動作例 0 i=4 NEXT-TO-TOP(S)= TOP(S)= pi=p4 p4 は左回り p4 を PUSH 1 p9 p7 p6 p5 2 p8 p4 p2 p4 stack S

87 Graham スキャン (Graham s scan) 動作例 0 i=5 NEXT-TO-TOP(S)= TOP(S)=p4 pi=p5 p4p5 は右回り p4 を POP p5 1 p9 p7 p6 2 p8 p4 p2 p4 stack S

88 Graham スキャン (Graham s scan) 動作例 0 i=5 NEXT-TO-TOP(S)= TOP(S)=p4 pi=p5 p4p5 は右回り p4 を POP p5 1 p9 p7 p6 2 p8 p4 p2 stack S

89 Graham スキャン (Graham s scan) 動作例 0 i=5 NEXT-TO-TOP(S)= TOP(S)= pi=p5 p5 は左回り p5 を PUSH p5 1 p9 p7 p6 2 p8 p4 p2 stack S

90 Graham スキャン (Graham s scan) 動作例 0 i=5 NEXT-TO-TOP(S)= TOP(S)= pi=p5 p5 は左回り p5 を PUSH p5 1 p9 p7 p6 2 p8 p4 p2 p5 stack S

91 Graham スキャン (Graham s scan) 動作例 0 i=6 NEXT-TO-TOP(S)= TOP(S)=p5 pi=p6 p5p6 は左回り p6 を PUSH p5 1 p9 p7 p6 2 p8 p4 p2 p5 stack S

92 Graham スキャン (Graham s scan) 動作例 0 i=6 NEXT-TO-TOP(S)= TOP(S)=p5 pi=p6 p5p6 は左回り p6 を PUSH p5 1 p9 p7 p6 2 p8 p4 p6 p5 stack S p2

93 Graham スキャン (Graham s scan) 動作例 0 i=7 NEXT-TO-TOP(S)=p5 TOP(S)=p6 pi=p7 p5p6p7 は左回り p7 を PUSH p6 p5 1 p9 p7 2 p8 p4 p6 p5 stack S p2

94 Graham スキャン (Graham s scan) 動作例 0 i=7 NEXT-TO-TOP(S)=p5 TOP(S)=p6 pi=p7 p5p6p7 は左回り p7 を PUSH p6 p5 1 p9 p7 2 p8 p4 p7 p6 p5 stack S p2

95 Graham スキャン (Graham s scan) 動作例 0 i=8 NEXT-TO-TOP(S)=p6 TOP(S)=p7 pi=p8 p6p7p8 は左回り p8 を PUSH p7 p6 p5 1 p9 2 p8 p4 p7 p6 p5 stack S p2

96 Graham スキャン (Graham s scan) 動作例 0 i=8 NEXT-TO-TOP(S)=p6 TOP(S)=p7 pi=p8 p6p7p8 は左回り p8 を PUSH p6 p5 1 p9 p7 p8 p7 p6 p5 stack S 2 p8 p2 p4

97 Graham スキャン (Graham s scan) 動作例 0 i=9 NEXT-TO-TOP(S)=p7 TOP(S)=p8 pi=p9 p7p8p9 は右回り p8 を POP p6 p5 1 p9 p7 p8 p7 p6 p5 stack S 2 p8 p2 p4

98 Graham スキャン (Graham s scan) 動作例 0 i=9 NEXT-TO-TOP(S)=p7 TOP(S)=p8 pi=p9 p7p8p9 は右回り p8 を POP p6 p5 p9 1 p7 2 p8 p4 p7 p6 p5 stack S p2

99 Graham スキャン (Graham s scan) 動作例 0 i=9 NEXT-TO-TOP(S)=p6 TOP(S)=p7 pi=p9 p6p7p9 は右回り p7 を POP p6 p5 1 p9 p7 2 p8 p4 p7 p6 p5 stack S p2

100 Graham スキャン (Graham s scan) 動作例 0 i=9 NEXT-TO-TOP(S)=p6 TOP(S)=p7 pi=p9 p6p7p9 は右回り p7 を POP p6 p5 1 p9 p7 2 p8 p4 p6 p5 stack S p2

101 Graham スキャン (Graham s scan) 動作例 0 i=9 NEXT-TO-TOP(S)=p5 TOP(S)=p6 pi=p9 p5p6p9 は右回り p9 を PUSH p6 p5 p9 1 p7 2 p8 p4 p6 p5 stack S p2

102 Graham スキャン (Graham s scan) 動作例 0 i=9 NEXT-TO-TOP(S)=p5 TOP(S)=p6 pi=p9 p5p6p9 は右回り p9 を PUSH p6 p5 p9 1 p7 2 p8 p4 p9 p6 p5 stack S p2

103 Graham スキャン (Graham s scan) 動作例 0 i=10 NEXT-TO-TOP(S)=p6 TOP(S)=p9 pi=0 p6p90 は右回り p9 を POP p6 p5 p9 1 p7 2 p8 p4 p9 p6 p5 stack S p2

104 Graham スキャン (Graham s scan) 動作例 0 i=10 NEXT-TO-TOP(S)=p6 TOP(S)=p9 pi=0 p6p90 は右回り p9 を POP p6 p5 p9 1 p7 2 p8 p4 p6 p5 stack S p2

105 Graham スキャン (Graham s scan) 動作例 0 i=10 NEXT-TO-TOP(S)=p5 TOP(S)=p6 pi=0 p5p60 は右回り p6 を POP p5 p9 p6 1 p7 2 p8 p4 p6 p5 stack S p2

106 Graham スキャン (Graham s scan) 動作例 0 i=10 NEXT-TO-TOP(S)=p5 TOP(S)=p6 pi=0 p5p60 は右回り p6 を POP p5 p9 p6 1 p7 2 p8 p4 p2 p5 stack S

107 Graham スキャン (Graham s scan) 動作例 0 i=10 NEXT-TO-TOP(S)= TOP(S)=p5 pi=0 p50 は右回り p5 を POP 1 p9 p7 p6 p5 2 p8 p4 p2 p5 stack S

108 Graham スキャン (Graham s scan) 動作例 0 i=10 NEXT-TO-TOP(S)= TOP(S)=p5 pi=0 p50 は右回り p5 を POP 1 p9 p7 p6 p5 2 p8 p4 p2 stack S

109 Graham スキャン (Graham s scan) 動作例 0 i=10 NEXT-TO-TOP(S)= TOP(S)= pi=0 0 は左回り 0 を PUSH 1 p9 p7 p6 p5 2 p8 p4 p2 stack S

110 Graham スキャン (Graham s scan) 動作例 0 i=10 NEXT-TO-TOP(S)= TOP(S)= pi=0 0 は左回り 0 を PUSH 1 p9 p7 p6 p5 2 p8 p4 p2 0 stack S

111 Graham スキャン (Graham s scan) 動作例 0 i=11 NEXT-TO-TOP(S)= TOP(S)=0 pi=1 01 は左回り 1 を PUSH 1 p9 p7 p6 p5 2 p8 p4 p2 0 stack S

112 Graham スキャン (Graham s scan) 動作例 0 i=11 NEXT-TO-TOP(S)= TOP(S)=0 pi=1 01 は左回り 1 を PUSH 1 p9 p7 p6 p5 2 p8 p4 1 0 stack S p2

113 Graham スキャン (Graham s scan) 動作例 0 i=12 NEXT-TO-TOP(S)=0 TOP(S)=1 pi=2 01 は右回り 1 を POP 1 p9 p7 p6 p5 2 p8 p4 1 0 stack S p2

114 Graham スキャン (Graham s scan) 動作例 0 i=12 NEXT-TO-TOP(S)=0 TOP(S)=1 pi=2 01 は右回り 1 を POP 1 p9 p7 p6 p5 2 p8 p4 p2 0 stack S

115 Graham スキャン (Graham s scan) 動作例 0 i=12 NEXT-TO-TOP(S)= TOP(S)=0 pi=2 01 は左回り 2 を PUSH 1 p9 p7 p6 p5 2 p8 p4 p2 0 stack S

116 Graham スキャン (Graham s scan) 動作例 0 i=12 NEXT-TO-TOP(S)= TOP(S)=0 pi=2 01 は左回り 2 を PUSH 1 p9 p7 p6 p5 2 p8 p4 2 0 stack S p2

117 Graham スキャン (Graham s scan) 動作例 0 以上で凸包が計算された スタック S は確かに, 凸包の頂点を反時計回りの順に含んでいる 1 p9 p7 p6 p5 2 p8 p4 2 0 stack S p2

118 Graham スキャン (Graham s scan) 補足説明 Ⅰ 偏角の大小比較 p2 p2 の に関する偏角が, の に関する偏角より大きい が p2 に対して時計回りの方向にある p2 が正 このように大小比較してソートすれば良い

119 Graham スキャン (Graham s scan) 補足説明 Ⅱ 右折, 左折の判定 p2がどちら回りなのか? 左折 右折 p2 が に関して時計回りか反時計回りかを判定すれば良い (33.1 節 p936 参照 ) p2 p2 p2 が に対して時計回りの時 右折反時計回りの時 左折

120 Graham スキャン (Graham s scan) 補足説明 Ⅱ 右折, 左折の判定 右折 例 : 右折の時 p2 (p2-) (-)>0 に対して p2 は時計回り p2 は右折

121 Graham スキャン (Graham s scan) 定理 33.1 Graham スキャンの正当性 Q 3 である点集合 Q について GRAHAM-SCAN を実行し, 終了したとき, スタック S はボトムからトップまで確かに CH(Q) の頂点を反時計回りに含んでいる. Proof ( 以下 ホワイトボードを交えながら説明する ) 2 行目より後, 点列 <,p2,,pm> を得る. i=2,3,,m に対して, 部分集合 Qi={,, pi} を定義する. Q-Qm に含まれる点は, に関する偏角が同じであるため取り除かれた点であり, それらの点は CH(Q) に入らず,CH(Qm)=CH(Q) である. よって, これは GRAHAM-SCAN が終了するとき, スタック S がボトムからトップまで反時計回りの順に CH(Qm) の頂点が積み重なるように構成されている, ということを示すのに十分である.,,pm が CH(Q) の頂点であると同時に,,,pi は全て CH(Qi) の頂点であるということに注意しよう.

122 Graham スキャン (Graham s scan) この証明には以下に示す ループの不変の性質を用いる : 6-9 行目のループの繰り返しの毎回のスタートにおいて, スタック S は確かにボトムからトップまで CH(Qi-1) の頂点を反時計回りの順に含むように構成されている.( 以下で証明 ) Initialization 最初に 6 行目を実行するとき, スタック S は確かに Q2=Qi-1 の頂点から構成され 3 点からなるこの集合は自身の凸包を形成するので, この不変の性質は成り立つ さらに, 頂点はボトムからトップまで反時計回りに現れる. Maintenance for ループの繰り返しに入ったとき, スタック S のトップは点 pi-1 であり, この点はこれ以前の繰り返しの終わり ( もしくは最初の繰り返しの前,i=3 のとき ) に PUSH されたものである. 7-8 行目の while ループが実行されたあとの, ただし 9 行目の pi がプッシュされる前の S のトップの点を pj とし,pk が S 上において pj の下にある点であるとする. この瞬間においては pj が S のトップの点であり, まだ pi を S にプッシュしておらず,S は確かに for ループの j の時の繰り返しの後に含んでいたのと同じ点を含んでいる.

123 Graham スキャン (Graham s scan) ループの繰り返しによって,S は確かに CH(Qj) の頂点を含んでおり, それらはボトムからトップに反時計回りの順に現れる. piがプッシュされる直前に注目することを続けよう. 図 33.8(a) で触れているように,pi の に関する偏角は pj のそれよりも大きいため, pkpjpi は左回り ( そうでなければ pj をPOPしなければならなかっただろう ) であり, S が確かに CH(Qj) の頂点を含んでいるので, 一度 pi をプッシュすると, スタックSは確かにCH(Qj {pi}) の頂点を, 今まで通りボトムからトップまで反時計回りの順に含むようになる. pj pk (a) pi の に関する偏角は pj のそれよりも大きく, 角 pkpjpi は左回りであるために, pi を CH(Q) に加えることで, 確かに CH(Qj {pi}) の頂点を得る. pi p2 図 33.8(a)

124 Graham スキャン (Graham s scan) さて,CH(Qj {pi}) が CH(Qi) と同じ点集合であることを示そう. ある点 pt を for ループの i 番目の繰り返しの間にPOPされた点であり, pr は pt がPOPされたときスタックSにおいて pt のすぐ下にある点と考える (pr は pj かもしれない ). prptpi は左回りではなく,pt の に関する偏角は pr のそれよりも大きい. 図 33.8(b) にあるように,pt は,pr,pi が形成する三角形の内部に, もしくは三角形の横になくてはならない ( しかしそれは三角形の頂点ではない ). pj pk pi pr (b) もし角 prptpi は左回りでないなら, pt は,pr,pi によって形成される三角形の内部, または横に存在することになり,CH(Qi) の頂点にはならない. pt p2 図 33.8(b)

125 Graham スキャン (Graham s scan) pt は Qi の他の 3 点によって形成される三角形の内部に存在するので, CH(Qi) の頂点とはなり得ないのは明らかである. よって pt は CH(Qi) の頂点ではないので, CH(Qi-{pt})=CH(Qi) を得る. pj pk pi pr (b) もし角 prptpi は左回りでないなら, pt は,pr,pi によって形成される三角形の内部, または横に存在することになり,CH(Qi) の頂点にはならない. pt p2 図 33.8(b)

126 Graham スキャン (Graham s scan) Pi を for ループにおける i 番目の繰り返しの間に POP された点の集合とする. Pi の全ての点に equality(33.1 節 ) が適用できるので, 繰り返しそれを適用することで CH(Qi-Pi)=CH(Qi) を示すことができる. ただし Qi-Pi=Qj {pi} であり, それゆえ CH(QjU{Pi})=CH(Qi-Pi)=CH(Qi)=CH(Qi) と結論付けることができる. ひとたび pi が PUSH されると, スタック S は確かにボトムからトップまで CH(Qi) の頂点を反時計回りの順に含むようになるということを示した. i をインクリメントすることによって次の繰り返しを維持するためのループの不変の性質が発生する. Termination ループが終了するとき,i=m+1 となり, したがってループの不変の性質はスタック S が確かに CH(Qm) の, つまり CH(Q) の頂点が反時計回りの順に格納されていることを意味する. これで証明は完了である.

127 Graham スキャン (Graham s scan) 計算量の吟味 n= Q として, グラハムスキャンが O(nlogn) 時間で終了するということを示す. GRAHAM-SCAN(Q) 1 let p 0 be the point in Q with the minimum y-coordinate, or the leftmost such point in case of a tie 2 let <p 1, p 2,, p m > be the remaining points in Q, sorted by polar angle in counterclockwise order around p 0 (if more than one point has the same angle, remove all but the one that is farthest from p 0 ) 3 PUSH(p 0,S) 4 PUSH(p 1,S) 5 PUSH(p 2,S) 6 for i 3 to m 7 do while the angle formed by points NEXT-TO-TOP(S), TOP(S), and p i makes nonleft turn 8 do POP(S) 9 PUSH(p i, S) 10 return S

128 Graham スキャン (Graham s scan) 計算量の吟味 n= Q として, グラハムスキャンが O(nlogn) 時間で終了するということを示す Line 1. Θ(n) 時間かかる GRAHAM-SCAN(Q) 1 let p 0 be the point in Q with the minimum y-coordinate, or the leftmost such point in case of a tie 2 let <p 1, p 2,, p m > be the remaining points in Q, sorted by polar angle in counterclockwise order around p 0 (if more than one point has the same angle, remove all but the one that is farthest from p 0 ) 3 PUSH(p 0,S) 4 PUSH(p 1,S) 5 PUSH(p 2,S) 6 for i 3 to m 7 do while the angle formed by points NEXT-TO-TOP(S), TOP(S), and p i makes nonleft turn 8 do POP(S) 9 PUSH(p i, S) 10 return S

129 Graham スキャン (Graham s scan) Line 2 偏角のソートするのにマージソートもしくはヒープソートを用い 計算量の吟味, 角度比較に33.1 節のcross-product-methodを用いるので,O(nlogn) 時間かかる n= Q として, グラハムスキャンが O(nlogn) 時間で終了するということを示す. ( 偏角が同じになる最遠点を除いてすべて取り除くのはトータルでO(n) 時間 ) GRAHAM-SCAN(Q) 1 let p 0 be the point in Q with the minimum y-coordinate, or the leftmost such point in case of a tie Θ(n) 2 let <p 1, p 2,, p m > be the remaining points in Q, sorted by polar angle in counterclockwise order around p 0 (if more than one point has the same angle, remove all but the one that is farthest from p 0 ) 3 PUSH(p 0,S) 4 PUSH(p 1,S) 5 PUSH(p 2,S) 6 for i 3 to m 7 do while the angle formed by points NEXT-TO-TOP(S), TOP(S), and p i makes nonleft turn 8 do POP(S) 9 PUSH(p i, S) 10 return S

130 Graham スキャン (Graham s scan) 計算量の吟味 n= Q として, グラハムスキャンが O(nlogn) 時間で終了するということを示す. GRAHAM-SCAN(Q) 1 let Line p be the point in Q with the minimum y-coordinate, O(1) 時間かかる or the leftmost such point in case of a tie Θ(n) 2 let <p 1, p 2,, p m > be the remaining points in Q, sorted by polar angle in counterclockwise order around p 0 O(nlogn) (if more than one point has the same angle, remove all but the one that is farthest from p 0 ) 3 PUSH(p 0,S) 4 PUSH(p 1,S) 5 PUSH(p 2,S) 6 for i 3 to m 7 do while the angle formed by points NEXT-TO-TOP(S), TOP(S), and p i makes nonleft turn 8 do POP(S) 9 PUSH(p i, S) 10 return S

131 Graham スキャン (Graham s scan) Line 6-9 m n-1 なので計算量の吟味,for ループの実行回数は高々 n-3 回 PUSHにはO(1) 時間かかるから, 各繰り返しは7-8 行目の whileループを除けば n= Q として, グラハムスキャンが O(nlogn) 時間で終了するということを示す. O(1) 時間かかるよって while ループを除けば,for ループ全体はO(n) 時間かかる GRAHAM-SCAN(Q) 1 let p 0 be the point in Q with the minimum y-coordinate, or the leftmost such point in case of a tie 2 let <p 1, p 2,, p m > be the remaining points in Q, sorted by polar angle in counterclockwise order around p 0 (if more than one point has the same angle, remove all but the one that is farthest from p 0 ) 3 PUSH(p 0,S) 4 PUSH(p 1,S) 5 PUSH(p 2,S) 6 for i 3 to m O(1) Θ(n) O(nlogn) 7 do while the angle formed by points NEXT-TO-TOP(S), TOP(S), and p i makes nonleft turn 8 do POP(S) 9 PUSH(p i, S) 10 return S

132 Graham スキャン (Graham s scan) 計算量の吟味 n= Q として, グラハムスキャンが O(nlogn) 時間で終了するということを示す. GRAHAM-SCAN(Q) 1 let p 0 be the point in Q with the minimum y-coordinate, or the leftmost such point in case of a tie Θ(n) 2 let <p 1, p 2,, p m > be the remaining points in Q, sorted by polar angle in counterclockwise order around p 0 O(nlogn) (if more than one point has the same angle, remove all but the one that is farthest from p 0 ) 3 PUSH(p 0,S) 4 PUSH(p 1,S) O(1) 5 PUSH(p 2,S) 6 for i 3 to m 7 do while the angle formed by points NEXT-TO-TOP(S), TOP(S), and p i makes nonleft turn 8 do POP(S) 9 PUSH(p i, S) O(n) ( ただし while ループは除く ) 10 return S? では,While ループの計算量はどうなるのか?

133 Line 行目の検査がO(1) 時間かかるので,POPの各呼び出しにはO(1) 時間かかる m n-1 m-2 n-3 より,while ループにかかる時間はアルゴリズム全体でO(n) 凸包を計算するアルゴリズム Graham スキャン (Graham s scan) 計算量の吟味 7 do while the angle formed by points NEXT-TO-TOP(S), TOP(S), and p i makes nonleft turn 8 do POP(S) 結論から言えば,while ループにかかる時間は O(n) となる これを示すのに, 集計法 (aggregation method) を用いる i=0,1,,m に対するそれぞれの点 pi はスタックに一度しか積まれない 各 PUSH 命令に対し,POP 命令は高々 1 回しか実行されない 少なくとも 3 点,,pm はスタックから決して POP されることはない 実際は高々 m-2 回の POP 命令が全体で実行される While ループの各繰り返しは POP 命令を 1 回実行 全体で高々 m-2 回の while ループの繰り返しが存在

134 Graham スキャン (Graham s scan) 計算量の吟味 n= Q として, グラハムスキャンが O(nlogn) 時間で終了するということを示す. GRAHAM-SCAN(Q) 1 let p 0 be the point in Q with the minimum y-coordinate, or the leftmost such point in case of a tie Θ(n) 2 let <p 1, p 2,, p m > be the remaining points in Q, sorted by polar angle in counterclockwise order around p 0 O(nlogn) (if more than one point has the same angle, remove all but the one that is farthest from p 0 ) 3 PUSH(p 0,S) 4 PUSH(p 1,S) O(1) 5 PUSH(p 2,S) 6 for i 3 to m 7 do while the angle formed by points NEXT-TO-TOP(S), TOP(S), and p i makes nonleft turn 8 do POP(S) 9 PUSH(p i, S) 10 return S O(n) ( ただし while ループは除く ) O(n) ( 全体で )

135 Graham スキャン (Graham s scan) 計算量の吟味 n= Q として, グラハムスキャンが O(nlogn) 時間で終了するということを示す. GRAHAM-SCAN(Q) 1 let p 0 be the point in Q with the minimum y-coordinate, or the leftmost such point in case of a tie Θ(n) 2 let <p 1, p 2,, p m > be the remaining points in Q, sorted by polar angle in counterclockwise order around p 0 O(nlogn) (if more than one point has the same angle, remove all but the one that is farthest from p 0 ) 3 PUSH(p 0,S) 4 PUSH(p 1,S) O(1) 5 PUSH(p 2,S) 6 for i 3 to m 7 do while the angle formed by points NEXT-TO-TOP(S), TOP(S), and p i makes nonleft turn 8 do POP(S) 9 PUSH(p i, S) 10 return S O(n) (6-9 行目全体で )

136 Graham スキャン (Graham s scan) 計算量の吟味 n= Q として, グラハムスキャンが O(nlogn) 時間で終了するということを示す. GRAHAM-SCAN(Q) 1 let p 0 be the point in Q with the minimum y-coordinate, or the leftmost such point in case of a tie 2 let <p 1, p 2,, p m > be the remaining points in Q, sorted by polar angle in counterclockwise order around p 0 (if more than one point has the same angle, remove all but the one that is farthest from p 0 ) 3 PUSH(p 0,S) O(nlogn) 4 PUSH(p 1,S) 5 PUSH(p 2,S) 6 for i 3 to m 7 do while the angle formed by points NEXT-TO-TOP(S), TOP(S), and p i makes nonleft turn 8 do POP(S) 9 PUSH(p i, S) 10 return S 結局,GRAHAM-SCAN 全体の計算量はソートの実行時間に依存 O(nlogn)

137 Graham スキャン (Graham s scan) 候補点をスタック S で管理しながら凸包問題を解く 入力集合 Q の各点はいったんスタックに入れられ,CH(Q) の頂点でない点は最終的にはスタックから取り除かれる アルゴリズム終了の時点で, スタックはCH(Q) の頂点だけを, 境界面上での反時計回りの出現順に含む Graham s scan 終了時のスタック 入力集合 Q={,,p2,,2} p6 p7 p6 p7 p4 p5 p2 p2 stack

138 Jarvis の行進法 (Jarvis s march) パッケージ包装 (package wrapping) ( またはギフト包装 (gift wrapping)) という技法により凸包を計算 イメージ図 : 物体 X 包装紙

139 Jarvis の行進法 (Jarvis s march) パッケージ包装 (package wrapping) ( またはギフト包装 (gift wrapping)) という技法により凸包を計算 イメージ図 : 包装紙

140 Jarvis の行進法 (Jarvis s march) パッケージ包装 (package wrapping) ( またはギフト包装 (gift wrapping)) という技法により凸包を計算 イメージ図 : 包装紙

141 Jarvis の行進法 (Jarvis s march) パッケージ包装 (package wrapping) ( またはギフト包装 (gift wrapping)) という技法により凸包を計算 イメージ図 : 包装紙

142 Jarvis の行進法 (Jarvis s march) パッケージ包装 (package wrapping) ( またはギフト包装 (gift wrapping)) という技法により凸包を計算 イメージ図 : Complete!! h を CH(Q) の頂点数として,O(nh) 時間で実行可能 h が o(logn) であるとき,Graham スキャンよりも漸近的に速い 包装紙

143 Jarvis の行進法 (Jarvis s march) より形式的には CH(Q) の頂点の系列 H={,, ph-1} を求める. 点集合 Q の中で最も y 座標が小さい点を とする. は に関して偏角最小の点,p2 は に関して偏角最小の点, は としていく. y 座標が最大の点 pk に到達したとき 凸包の右側チェインが完成. 左側チェインを構成するために,pk に関して負の x 軸からの偏角が最小の点として pk+1 を選択. これを に戻ってくるまで続ける. 左側チェイン 右側チェイン H={,, p4} p4 p2

144 Jarvis の行進法 (Jarvis s march) 動作例 入力集合 Q

145 Jarvis の行進法 (Jarvis s march) 動作例 集合 Q に含まれる点のうち, y 座標の最も小さい点を とする

146 Jarvis の行進法 (Jarvis s march) 動作例 に関する各点の偏角を比較

147 Jarvis の行進法 (Jarvis s march) 動作例 に関する負の偏角が最小である点を次の頂点とする

148 Jarvis の行進法 (Jarvis s march) 動作例 に関する偏角が最小である点を次の頂点とする

149 Jarvis の行進法 (Jarvis s march) 動作例 に関する各点の偏角を比較

150 Jarvis の行進法 (Jarvis s march) 動作例 に関する偏角が最小である点を次の頂点とする

151 Jarvis の行進法 (Jarvis s march) 動作例 に関する偏角が最小である点を次の頂点とする p2

152 Jarvis の行進法 (Jarvis s march) 動作例 p2 に関する各点の偏角を比較 p2

153 Jarvis の行進法 (Jarvis s march) 動作例 p2 に関する偏角が最小である点を次の頂点とする p2

154 Jarvis の行進法 (Jarvis s march) 動作例 p2 に関する偏角が最小である点を次の頂点とする p2

155 Jarvis の行進法 (Jarvis s march) 動作例 右側チェイン y 座標が最大の点 に到達右側チェインが完成 p2

156 Jarvis の行進法 (Jarvis s march) 動作例 右側チェイン に関する各点の負の偏角を比較 p2

157 Jarvis の行進法 (Jarvis s march) 動作例 右側チェイン に関する負の偏角が最小である点を次の頂点とする p2

158 Jarvis の行進法 (Jarvis s march) 動作例 右側チェイン に関する負の偏角が最小である点を次の頂点とする p2 p4

159 Jarvis の行進法 (Jarvis s march) 動作例 右側チェイン p4 に関する各点の負の偏角を比較 p2 p4

160 Jarvis の行進法 (Jarvis s march) 動作例 右側チェイン p4 に関する負の偏角が最小である点を次の頂点とする p2 p4

161 Jarvis の行進法 (Jarvis s march) 動作例 右側チェイン p4 に関する負の偏角が最小である点を次の頂点とする p2 p4

162 Jarvis の行進法 (Jarvis s march) 動作例 左側チェイン右側チェイン に到達左側チェインが完成 p2 p4

163 Jarvis の行進法 (Jarvis s march) 動作例 点集合 Q の凸包が計算された p2 p4

164 Jarvis の行進法 (Jarvis s march) Jarvis の行進法を左右のチェインを別々に構成するのではなく実行することも可能 このような実行方法では, 選ばれた最後の凸包の辺を覚えておき, 凸包の辺の角度の列が真に増加列であることが必要になる (0 から 2π の範囲で ) 別々にチェインを構成する利点 角度を明示的に計算する必要がない 計算量の吟味 偏角の比較は 33.1 節の技法を用いると O(1) 時間でできる ある参照点に関する n 個の点の偏角の最小値は O(n) 時間で計算可能 アルゴリズム全体は O(nh) 時間で計算可能

165 CONTENTS 33.4 最近点対の発見 (Finding the pair of closest points) 最近点対とは? 最近点対を計算するアルゴリズム

166 CONTENTS 33.4 最近点対の発見 (Finding the pair of closest points) 最近点対とは? 最近点対を計算するアルゴリズム

167 最近点対 (pair of closest points) とは? n 2 点の集合 Q の中の,2 点間のユークリッド距離が最小である組 n 点集合 Q,p2 のユークリッド距離 : x 1 x (y 1 y 2 ) 2 (x1,y1) p2(x2,y2) 最近点対 交通制御システムで, 衝突を検出すること等に応用されている

168 CONTENTS 33.4 最近点対の発見 (Finding the pair of closest points) 最近点対とは? 最近点対を計算するアルゴリズム

169 凸包を計算する様々なアルゴリズムの紹介 1. 腕力法 (brute-force method) 2. 分割統治法 (divided-and-conquer method)

170 最近点対を計算するアルゴリズム 腕力法 (brute-force method) 力づくで強引な方法 単に全ての n 2 =Θ(n2 ) 通りの点対を調べる 参照点 ある参照点と他の点全ての距離を計算し, 最小値を保持しながら参照点を変えていく とてつもなく時間がかかる

171 最近点対を計算するアルゴリズム 分割統治法 (divide-and-conquer algorithm) アルゴリズム全体の計算量を T(n) とすると,T(n)=2T(n/2)+O(n) T(n)=O(nlogn) ( 口頭で説明 ) 点集合全体を分割し,2 つの部分集合をつくる それらの部分集合の最近点対を再帰的に計算

172 分割統治法 (divide-and-conquer method) n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の最近点対を再帰的に計算する. 求める最近点対は, 再帰呼び出しで見つかった点対 または, 部分集合の一方に 1 点を, もう一方に 1 点を持つ点対である. イメージ的には 分割 n 点集合 右側の最近点対 左側の最近点対 2 つの部分集合の片方ずつに 1 つずつ要素を持つ最近点対

173 分割統治法 (divide-and-conquer method) n 点の集合を, 左から n/2 個の点からなる集合と右から n/2 個の点からなる集合の 2 つに分割し, これらの部分集合の最近点対を再帰的に計算する. 求める最近点対は, 再帰呼び出しで見つかった点対 または, 部分集合の一方に 1 点を, もう一方に 1 点を持つ点対である. イメージ的には n 点集合 求めるべき最近点対 アルゴリズム全体の計算量を T(n) とすると,T(n)=2T(n/2)+O(n) T(n)=O(nlogn)

174 分割統治法 (divide-and-conquer method) 具体的には 部分集合 P P =5 毎回の再帰呼び出しで部分集合 P Q を入力とする X[0],Y[1] 部分集合 P の全ての点を含む配列 X と Y を用いる X は x 座標が昇順にソートされている Y は y 座標の昇順にソートされている X[1],Y[4] X[0],Y[1] X[4],Y[2] 再起呼び出しの段階でソートは行わない ソートを行うと実行時間の再起式は T(n)=2T(n/2)+O(logn) T(n)=O(nlog 2 n) となってしまう X[2],Y[0] O(nlogn) とするためにはソーティングを実行せずに整列性を維持することが必要 そこでプリソーティング (presorting) という考え方を用いる ( 後ほど説明 )

175 分割統治法 (divide-and-conquer method) アルゴリズムの動作 ( 入力は P,X,Y) P 3 のとき 腕力法により P 2 個の点すべての点対を調べて最も近い点対を返す P >3 のとき 再起呼び出しにより分割統治法を実行

176 分割統治法 (divide-and-conquer method) アルゴリズムの動作 ( 入力は P,X,Y) 分割 点集合 P X[2],Y[8] X[8],Y[9] X[5],Y[7] X[7],Y[6] X[4],Y[5] X[6],Y[4] X[0],Y[2] X[1],Y[0] X[3],Y[3] X[9],Y[1]

177 分割統治法 (divide-and-conquer method) アルゴリズムの動作 ( 入力は P,X,Y) 分割 点集合 P を 2 つの集合 P L と P R に分割 集合 P L 集合 P R X[2],Y[8] X[8],Y[9] X[5],Y[7] X[7],Y[6] X[4],Y[5] X[0],Y[2] X[1],Y[0] X[3],Y[3] X[6],Y[4] X[9],Y[1]

178 分割統治法 (divide-and-conquer method) アルゴリズムの動作 ( 入力は P,X,Y) 分割 垂直線 l 集合 P L 集合 P R 点集合 P を 2 つの集合 P L と P R に分割 P L の点は全て直線 l の左に P R の点は全て直線 l の右にくるような垂直線 l を求める X[2],Y[8] X[8],Y[9] X[5],Y[7] X[7],Y[6] X[4],Y[5] X[0],Y[2] X[1],Y[0] X[3],Y[3] X[6],Y[4] X[9],Y[1]

179 分割統治法 (divide-and-conquer method) アルゴリズムの動作 ( 入力は P,X,Y) 分割 垂直線 l 集合 P L 集合 P R 配列 X を X L と X R に分割し, それぞれ P L と P R の点を x 座標の昇順に含むようにする X L [2],Y L [4] X R [0],Y R [3] X R [3],Y R [4] 同様に配列 Y を Y L と Y R に分割し, それぞれ P L と P R の点を y 座標の昇順に含むようにする X R [2],Y R [2] X L [4],Y L [3] X R [1],Y R [1] X L [0],Y L [1] X L [3],Y L [2] X L [1],Y L [0] X R [4],Y R [0]

180 分割統治法 (divide-and-conquer method) アルゴリズムの動作 ( 入力は P,X,Y) 統治 垂直線 l 集合 P L 集合 P R P を P L と P R に分割後, 再帰呼び出しを 2 回行う ( 簡単のためこれ以上の分割を省略 ) 1 回目 ( 入力 P L,X L,Y L ) では P L における最近点対を X L [2],Y L [4] X R [0],Y R [3] X R [3],Y R [4] 2 回目 ( 入力 P R,X R,Y R ) では P R における最近点対を X L [4],Y L [3] P R の最近点対 X R [2],Y R [2] それぞれ求める P L の最近点対 X R [1],Y R [1] X L [0],Y L [1] X L [3],Y L [2] X L [1],Y L [0] X R [4],Y R [0]

181 分割統治法 (divide-and-conquer method) アルゴリズムの動作 ( 入力は P,X,Y) 統治 垂直線 l P L と P R に対して求められた最近点対の距離をそれぞれ δ L,δ R とし, 集合 P L 集合 P R X L [2],Y L [4] X R [0],Y R [3] X R [3],Y R [4] X L [4],Y L [3] δ R X R [2],Y R [2] X L [0],Y L [1] X L [3],Y L [2] δ L X R [1],Y R [1] X L [1],Y L [0] X R [4],Y R [0]

182 分割統治法 (divide-and-conquer method) アルゴリズムの動作 ( 入力は P,X,Y) 統治 垂直線 l P L と P R に対して求められた最近点対の距離をそれぞれ δ L,δ R とし, 集合 P L 集合 P R δ =min(δ L,δ R ) とする X L [2],Y L [4] X R [0],Y R [3] X R [3],Y R [4] X L [4],Y L [3] δ X R [2],Y R [2] X R [1],Y R [1] X L [0],Y L [1] X L [3],Y L [2] X L [1],Y L [0] X R [4],Y R [0]

183 分割統治法 (divide-and-conquer method) アルゴリズムの動作 ( 入力は P,X,Y) 統合 垂直線 l 集合 P L 集合 P R 最近点対は先ほど見つけた距離 δ の点対もしくは, 1 点を P L に, もう 1 点を P R にもつ距離 δ の点対 このアルゴリズムではそのような点があるかを判定する ( 判定法については後ほど説明 ) X L [2],Y L [4] X R [0],Y R [3] X R [3],Y R [4] X L [4],Y L [3] δ X R [2],Y R [2] この場合は δ <δ となる距離 δ の点対が存在したがって距離 δ の点対が返される δ X R [1],Y R [1] return X L [0],Y L [1] X L [3],Y L [2] X L [1],Y L [0] X R [4],Y R [0]

184 分割統治法 (divide-and-conquer method) 判定法 距離が δ 未満の点対が存在する場合, それらの 2 点は直線から δ 単位以内にあるはず P L P R 2δ δ p L p R l 図 33.12(a) 図 33.12(a) に示すように, それら 2 点は直線 l を中心とする幅 2δ の垂直帯領域にあるはず

185 分割統治法 (divide-and-conquer method) そのような点対が存在すれば必ず見つけるために, 以下のようなことを行う 垂直線 l 1. 配列 Y から幅 2δ の垂直帯領域にないすべての点を取り除いて, 配列 Y を作る配列 Y は Y と同様に y 座標に関してソートされている P L P R X L [2],Y L [4] X R [0],Y R [3] X R [3],Y R [4] X L [4],Y L [3] δ X R [2],Y R [2] X R [1],Y R [1] X L [0],Y L [1] X L [3],Y L [2] X L [1],Y L [0] X R [4],Y R [0]

186 分割統治法 (divide-and-conquer method) そのような点対が存在すれば必ず見つけるために, 以下のようなことを行う 垂直線 l 1. 配列 Y から幅 2δ の垂直帯領域にないすべての点を取り除いて, 配列 Y を作る配列 Y は Y と同様に y 座標に関してソートされている P L P R X L [2],Y L [4] X R [0],Y R [3] X R [3],Y R [4] X L [4],Y L [3] δ X R [2],Y R [2] X R [1],Y R [1] X L [0],Y L [1] X L [3],Y L [2] X L [1],Y L [0] 2δ X R [4],Y R [0]

187 分割統治法 (divide-and-conquer method) そのような点対が存在すれば必ず見つけるために, 以下のようなことを行う 垂直線 l 1. 配列 Y から幅 2δ の垂直帯領域にないすべての点を取り除いて, 配列 Y を作る配列 Y は Y と同様に y 座標に関してソートされている P L P R Y [2] 後々の比較のために残しておく Y [1] δ Y [0] 2δ

188 分割統治法 (divide-and-conquer method) そのような点対が存在すれば必ず見つけるために, 以下のようなことを行う P L 垂直線 l P R 2. 配列 Y の各点 p について,p から δ 単位内にある Y の点を求める後々証明することだが,Y において p に続く 7 点だけを考えれば良い p からこの 7 点までの距離を計算し,Y のすべての点対についてそれまでに見つかった最近点対の距離 δ の履歴を管理しておく Y [1] Y [2] δ p=y [0] 最近点対の距離 δ =Y [1] Y [0] Y [0] 2δ

189 分割統治法 (divide-and-conquer method) そのような点対が存在すれば必ず見つけるために, 以下のようなことを行う P L 垂直線 l P R 2. 配列 Y の各点 p について,p から δ 単位内にある Y の点を求める後々証明することだが,Y において p に続く 7 点だけを考えれば良い p からこの 7 点までの距離を計算し,Y のすべての点対についてそれまでに見つかった最近点対の距離 δ の履歴を管理しておく Y [1] Y [2] δ p=y [0] 最近点対の距離 δ =Y [1] Y [0] δ Y [0] 2δ

190 分割統治法 (divide-and-conquer method) そのような点対が存在すれば必ず見つけるために, 以下のようなことを行う P L 垂直線 l P R 2. 配列 Y の各点 p について,p から δ 単位内にある Y の点を求める後々証明することだが,Y において p に続く 7 点だけを考えれば良い p からこの 7 点までの距離を計算し,Y のすべての点対についてそれまでに見つかった最近点対の距離 δ の履歴を管理しておく Y [2] δ p=y [0] 最近点対の距離 δ =Y [1] Y [0] Y [1] Y [0] δ 2δ

191 分割統治法 (divide-and-conquer method) そのような点対が存在すれば必ず見つけるために, 以下のようなことを行う P L 垂直線 l P R 2. 配列 Y の各点 p について,p から δ 単位内にある Y の点を求める後々証明することだが,Y において p に続く 7 点だけを考えれば良い p からこの 7 点までの距離を計算し,Y のすべての点対についてそれまでに見つかった最近点対の距離 δ の履歴を管理しておく Y [1] Y [2] Y [0] δ p=y [1] 最近点対の距離 δ =Y [1] Y [0] δ 2δ

192 分割統治法 (divide-and-conquer method) そのような点対が存在すれば必ず見つけるために, 以下のようなことを行う P L 垂直線 l P R 3. δ <δ の場合, この垂直帯領域は再帰呼び出しで見つけられたものより近い点対を確かに含んでいるそこで, この点対とその距離 δ を返すそうでなければ, 再帰呼び出しで見つかった最近点対とその距離 δ を返す Y [1] δ Y [2] Y [0] δ 左図より δ <δ したがって Y [0],Y [1] とその距離 δ が返る return 2δ この説明では O(nlogn) の実行時間を達成するために必要になる実行上の詳細な部分を省略しているアルゴリズムの正当性を説明したあとで, この目標の限界を達成するためのアルゴリズムの実行法を示す

193 分割統治法 (divide-and-conquer method) 正当性 アルゴリズムは次の2 点を除いて明白 1. P 3 のときのアルゴリズムの正当性 これ以上再帰を行えないことによって,1 点からなる部分問題を解かなくてもいいということがわかる 2. 配列 Y において, 各点に続く 7 点だけを調べれば良い 以下でこれを証明していく

194 分割統治法 (divide-and-conquer method) 正当性 再起のとあるレベルにおいて最近点対が p L P L と p R P R であるとする p L と p R の距離は真に δ より小さい p L は直線 l またはその左にあり,δ 単位以上離れていない p R は直線 l またはその右にあり,δ 単位以上離れていない p L と p R は互いに垂直方向に δ 単位以内にある p L と p R は直線 l を中心とする δ 2δ の長方形の中にある P L P R 2δ δ p L p R l 図 33.12(a)

195 分割統治法 (divide-and-conquer method) 正当性 δ 2δ の長方形の中に P の点が高々 8 個しかないことを示す この長方形の δ δ の正方形を考える P L 内の点はすべて少なくとも δ だけ離れている 正方形の中には高々 4 点しか存在しない (P R も同様 ) 長方形内には P の点が高々 8 点しか存在し得ない δ P L P R δ 配列 Y の各点に続く 7 点だけを調べれば良いことを示す 配列 Y において p L は p R よりも前にあると仮定する 一般性は失われない p L が配列 Y においてどんな前にあり,p R がどんな後に あろうとも p R は p L に続く 7 個の位置のどれかにある δ 以上で, 最近点対アルゴリズムの正当性が示された 図 33.12(b) 重複点 : 一方が P L 上にあり もう一方が P R 上にある 重複点 : 一方が P L 上にあり もう一方が P R 上にある

196 分割統治法 (divide-and-conquer method) 実現性と実行時間 主な難しさは以下の 2 点である 1. 再帰呼び出しで渡される配列 X L, X R, Y L, Y R が座標の順にソートされていること 2. Y が y 座標でソートされていること もし以上の2つが保証されるのなら, 集合 PをP L とP R に分割するのは線形時間で出来る 各呼び出しにおいてソート済みの配列からソートされた部分集合をどうやって形成するかが鍵 ( 例 : PをP L とP R に分割した後,y 座標でソートされた配列 Y L とY R を線形時間で作らなければならない ) 節で述べたマージソートの手続きMERGEとは逆の方法を取ることで条件を満たすようにする

197 分割統治法 (divide-and-conquer method) 実現性と実行時間 その考えを説明したのが以下の擬似コードである 1 length[y L ] length[y R ] 0 2 for i 1 to length[y] 3 do if Y[i] P L 4 then length[y L ] length[y L ] Y[length[Y L ]] Y[i] 6 else length[y R ] length[y R ] Y[length[Y R ]] Y[i]

198 分割統治法 (divide-and-conquer method) 実現性と実行時間 Line 2-7 for ループその考えを説明したのが以下の擬似コードである配列 Yの点を順に調べていく 1 length[y L ] length[y R ] 0 2 for i 1 to length[y] 3 do if Y[i] P L 4 then length[y L ] length[y L ] Y[length[Y L ]] Y[i] 6 else length[y R ] length[y R ] Y[length[Y R ]] Y[i]

199 分割統治法 (divide-and-conquer method) 実現性と実行時間 その考えを説明したのが以下の擬似コードである 1 length[y L ] length[y R ] 0 2 for i 1 to length[y] 3 do if Y[i] P L 4 then length[y L ] length[y L ] Y[length[Y L ]] Y[i] 6 else length[y R ] length[y R ] Y[length[Y R ]] Y[i] Line 3-5 点 Y[i] が P L にあればそれを Y R の最後に追加する

200 分割統治法 (divide-and-conquer method) 実現性と実行時間 その考えを説明したのが以下の擬似コードである 1 length[y L ] length[y R ] 0 2 for i 1 to length[y] 3 do if Y[i] P L 4 then length[y L ] length[y L ] Y[length[Y L ]] Y[i] 6 else length[y R ] length[y R ] Y[length[Y R ]] Y[i] Line 6-7 そうでなければそれを Y R の最後に追加する

201 分割統治法 (divide-and-conquer method) プリソーティング (presorting) と計算量点集合 Q の点を一度だけ, 最初の再帰呼び出しの前にソートしておくだけで良い プリソーティングのために余分に O(nlogn) の時間がかかるが, 再帰の各ステップでは再帰呼び出し以外では線形時間しかかからない T(n) を各再帰ステップの実行時間とし,T (n) を全体の実行時間とすると, T (n)=t(n)+o(nlogn) 及び, T(n)= 2T n + O n n > 3 2 O 1 n 3 を得るしたがって,T(n)=O(nlogn) より T (n)=o(nlogn) を得る