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

1.3

 賢い方式

■

3

式もなさそうだ。

1.2

 素朴解

凸包は明らかに、

3

個以上の点集合で存在する。しかし、どのように構成すれば

よいだろうか。次のようなアイデアを考えよう。元の点集合から任意の

3

点を選び、

三角形を作る。残りの

n

−

3

点のいずれかがこの三角形の内部に含まれるなら、そ

れらは凸包の一部ではない。この処理を一般化したものを疑似コードを使って記述

する。本書に登場するアルゴリズムには同様の記述を使う。

遅い凸包

Slow Hull

最良 平均 最悪

O(n

4

)

slowHull (P)

foreach p0 in P do

foreach p1 in {P

-

p0} do

foreach p2 in {P

-

p0

-

p1} do

❶

点

p0, p1, p2

は三角形になる。

foreach p3 in {P

-

p0

-

p1

-

p2} do

if p3

が

Triangle(p0,p1,p2)

に含まれる

then

p3

を内部とマーク

❷

内部と印されていない点は凸包上にある。

すべての非内部点

in P

で配列

A

を作る

A

の中で最左点

left

を決定する

left

を通る鉛直線となす角度で

A

をソートする

❸

角度は

–

90

から

90

（度）。

return A

なぜこの方式が非効率なのかを示す数学的解析手法について次章で説明する。こ

の疑似コードは、入力集合（図1-2で凸包を作ったものを含む）に正解を与えるス

テップを説明している。しかし、これが最良だろうか。

1.3

 賢い方式

本書の多くのアルゴリズムは、既存のコード ...