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

9.3

 凸包走査

■

289

1

なら、

p

は内部にあり削除できる。実装では、線分

s

が正確に極四辺形の頂点と交

差するような特別な場合も扱う。この計算は固定ステップなので、

O(1)

であり、全

点に対する

Akl-Toussaint

ヒューリスティックスは、

O(n)

となる。巨大なランダム

な点集合例では、初期の集合から半分近くの点を除くことができ、アルゴリズム全

体でコストのかかる整列化の処理が大幅に削減される。

9.3.4

 分析

単位正方形からランダムに生成した

2

次元の点集合上で

100

回試行した。最良と

最悪の試行を棄却した残りの

98

試行の平均時性能結果を表 9-2に示す。この表は、

ヒューリスティックスを実行するときの平均時間の内容を示すだけでなく、なぜ

凸

包走査

が効率的なのか、背後にある理由を示している。

入力集合のサイズが増えると、

Akl-Toussaint

ヒューリスティックスでほぼ半数

の点を削除できる。驚くべきことに、凸包上の点の

個数は少ない。表9-2の第

2

列は、

凸包上の点の個数が

O(log n)

になるという主張を裏付けるものだ（

Preparata and

Shamos, 1985

）。当然ながら、分布が重要になる。単位円から一様に点を選べば、

凸包の点の個数は

n

の立方根のオーダーになる。

表9-2　実行時間（ミリ秒）と適用されたAkl-Toussaintのヒューリスティックス

N

凸包の点の

平均個数

計算

平均時間

Akl-Toussaint

により削除された

点の平均個数

Akl-Toussaintの