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

9.2

 凸包

■

283

9.1.3

 タスクの性質

静的なタスクでは、ある特定の入力データセットに対して、要求に応じた答えを

1

つ返せばよい。しかし、動的なタスク状況では、次のように問題へのアプローチ

を変える必要がある。

●

いくつかのタスクが同じ入力データに対して要求される場合は、入力データ

を前処理して、各タスクの効率を改善する。

●

入力データセットが変化するなら、変更や削除に対して柔軟に対応できる

データ構造を検討する。

動的なタスクでは、入力集合に対する変更に応じて、伸縮自在なデータ構造が要

求される。固定長配列は静的タスクには適しているが、動的タスクでは、情報を共

通の目的に適う、リンク付きリストやスタックの形態でまとめておく必要がある。

9.1.4

 仮定

ほとんどの計算幾何学問題について、効率的な解は、入力集合（または行うタス

ク）に対する仮定と不変量の分析から始まる。例えば、次のようになる。

●

線分の入力集合に対して、水平な線分、または垂直な線分があり得るか。

●

点の集合に対して、

3

点が共線か（すなわち、平面上で同じ数学的な直線上に

あるか）。そうでないなら、直線は

一般の位置

（

general position

）にあると言

われ、多くのアルゴリズムを単純化できる。

●

入力集合は、一様分布した点からなるか。歪みがあったり、クラスターを形

成して、アルゴリズムの最悪時の振る舞いを招く危険性があるか。

本章で紹介したアルゴリズムの多くは、境界で異常な状態になり、実装が難しい

課題となる。コード例では ...