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

290

■

9

章 計算幾何学

凸包走査

で外積を計算するときに、浮動小数点算術の問題が出てくる。外積の

0

との比較

cp

＜

0

を厳密に行う代わりに、

PartialHull

では、δを

10

−

9

として、

cp

＜δで判定する。

9.3.5

 変形

凸包走査

の整列処理部分は、点が既に整列されていることがわかれば省略できる。

この場合、

凸包走査

は

O(n)

の性能となり得る。そうではなくても、入力点が一様

分布に従うなら、

バケツソート

（

4

章の

バケツソート

の項目参照）を使って、

O(n)

性

能を達成できる。その他の変形には、クイック凸包（

QuickHull

）

(Preparata and

Shamos, 1985)

と呼ばれるものがあり、

クイックソート

が使う「分割統治」法を用い

て、凸包を計算する。

もう

1

つ、最後の変形として考えるべきものがある。

凸包走査

は実は上側の凸包

を構成するときに、整列された配列を必要としない。

P

のすべての点を

x

座標の一

番小さいものから大きいも

のまで順に反復処理する必要があるだけだ。この振る

舞いは、

P

の点の二分ヒープを作り、ヒープから最小要素を取り除くことに対応す

る。取り除いた点をリンク付きリストに貯えれば、リンク付きリストから点を「読

み取る」だけで右から左へと逆順に点を処理することができる。この変形（図9-5の

Heap

で示す）のコードは、本書のコードリポジトリから入手できる

＊

1

。

図9-5に示した性能の結果は、次のような

2

種類のデータセット分布から得られ

た。

円形データ（Circledata）

n

個の点は、 ...