Algorithms/ComputationalGeometry - tmura's note

計算幾何

代表的な問題

コンビニの出店問題（ボロノイ分割問題）

与えられたボロノイ図において、新規の母点に対する領域の面積が最大になるように、
その場所を決めること。実は、よいアルゴリズムは知られていない。

ボロノイ図

平面上の点（母点 (generating point)）の集合が与えられたときに、

その平面を直線で母点の数と同じ領域に分割したもので、

各領域の内部には与えられた母点の中のいずれか１つが入っていて、

その母点によって支配されるという。

各領域の中の任意の場所からもっとも近い母点は、その領域内の母点である。

美術館問題 (Art Gallery Problem)

単純多角形（穴のない多角形）のフロアに対して、
できるだけ少ない監視員で全ての場所を見渡せるような監視員の配置の仕方を考える問題。

定理

単純角形の監視に必要な監視員の数は、最大でも人で十分である。

---

Algorithms