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

282

■

9

章 計算幾何学

し

2

章で論じたように、浮動小数点演算で生じる丸め誤差といった重要な問題は、

本章のアルゴリズムにも大いに関係する。

9.1.2

 計算

一般に、表9-1に示すような空間の問題について、計算幾何学では

3

種類の典型

的なタスクが行われる。

クエリ

望ましい制約（例えば、最も近いもの、最も遠いもの）に基づいて、入力

集合から存在する要素を選ぶ。この作業は、

5

章で論じた探索アルゴリ

ズムに直接関係し、次の

10

章でも扱う。

計算

入力集合（例えば、線分）に一連の計算を行って、入力集合の要素から特

定の幾何学的構造（例えば、線分間の交差）を生成する。

前処理

豊富なデータ構造の中に入力集合を埋め込んで、一連の質問に答えられ

るようにする。言い換えると、前処理の結果は、他の質問に対する入力

として用いられる。

表9-1　計算幾何学問題とその応用

計算幾何学の問題 実世界での応用

与えられた点に最も近い点を見つける。 与えられた車の位置から最も近いガソリンスタ

ンドを見つける。

与えられた点から最も遠い点を見つける。 救急車の拠点に対して、与えられた医療機関の

集合の中で最も遠い病院を見つけて、最悪時の

搬送時間を決める。

多角形が単純（すなわち、どの連続していない

辺同士も点を共有しない）かどうか決める。

絶滅危機種の動物に、その位置を知らせる無線

発信機を付ける。科学者は縄張りを見つけるた

めに、その動物が一度通った道をいつまた通る

か調べたい。

点の集合を含む最小円を計算する。点の集合に

対して、それらの中にあって ...