アルゴリズムクイックリファレンス 第2版

4

■

1

章 アルゴリズムで考える

1.3.1

 貪欲法

凸包を

1

点ずつ構成する方法を示す。

1. P

で最も低い位置の点

low

を見つけて、

P

から取り除く。この

low

は凸包の一

部になることが自明である。

2. low

を通る鉛直線からの角度の降順で、残っている

n

−

1

個の点をソートす

る。これらの角度の範囲は、鉛直線の左側

90

度から右側−

90

度になる。

p

n

−

2

が最右点、

p

0

が最左点である。図1-3 では、鉛直線を太い線、角度は細い線

で示す。

3. {p

n

−

2

, low, p

0

}

という順序の

3

点からなる部分凸包から出発する。部分凸包

に

p

1

から

p

n

−

3

までの各々を追加して凸包を拡張できないか考慮する。部分

凸包の最後の

3

点が左回りになったら、その部分凸包は誤った点を含んでい

ることになるので、最後から

2

つ目の点を取り除く。

4. p

n

−

2

までのすべての点を考慮したら、部分凸包は完了する。図1-3 参照。

図1-3　貪欲法を用いて構成した凸包

1.3.2

 分割統治法

P

のすべての点を

x

座標で左から右へとソートすれば、（

y

座標で分けて）問題を半

分に分割できる。このソートした集合に対して、まず上側の部分凸包を左から右へ、

p

0

から

p

n

−

1

まで時計回りに計算する。次に、下側の部分凸包を同じ点集合に対して

右から左、

p

n

−

1

から

p

0

まで再度時計回りに構成する。

9

章で述べる

凸包走査

（

Convex