計算幾何学
これに分類される問題は、いくつか入力が与えられた状態で、それに対応する出力を構築または計算することが要求される。この種の基本的な問題として
凸包: 与えられた点の集合に対して、それらを全て含む最小の凸多角形・凸集合を計算する問題。ギフト包装法など。
線分交叉問題: 与えられた線分の集合に対して、それらの交点を求める問題。
ドロネー三角形分割
ボロノイ図: 与えられた点の集合に対して、それらの中で最も近い点に代表される部分に属するように空間を分割する問題。
線型計画問題
最近接点探索: 与えられた点の集合に対して、その中で最も互いの距離が短いふたつを選び出す問題。
ユークリッド的最短経路問題: (多面体の障害物がある)ユークリッド空間において、与えられた二点を最短経路で結ぶ問題。
多角形の三角形分割: 与えられた多角形を、その内部にある三角形に分割する問題。
などが挙げられる。この種の問題に対する組合せ論的な計算量は、与えられた問題事例が要求する時間と空間(計算機のメモリ)によって評価される。
計算幾何学の書籍一覧
en:List of books in computational geometry