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

6

■

1

章 アルゴリズムで考える

2

つの凸包を縫い合わせ、これらの

2

直線で作られる四辺形の内部に含まれる線分

を取り除いて、凸包ができる。

1.3.4

 近似法

これまで述べた改善でも、凸包を計算するためには、打ち破れない、ある性能の

下限が存在する。しかし、正確な解を計算しなくても、誤差が正確に把握できて、

かつ迅速に計算できる近似解で十分なこともあるだろう。

Bentley-Faust-Preparata

アルゴリズムは、点集合を垂直片に分割することに

よって、凸包を近似する。各垂直片では、

y

座標に基づいて最大値と最小値を見つ

ける（それらの点を四角で図1-6に示した）。点集合

P

の最左点と最右点とともに、

これらの極値を縫い合わせて凸包を作る。こうすると、図1-6の点

p

1

からわかるよ

うに、凸包の外になる点も出てくる。

図1-6　近似計算で作られた凸包

1.3.5

 一般化

より一般的な問題を解くことができると、元の問題を解くのにその解をすぐ変換

できるということがよくある。ボロノイ図（

Preparata and Shamos, 1993

）は、平