幾何的対象のアルゴリズム的取扱い ぱらぱらめくる『Handbook of Discrete and Computational Geometry』
- 凸包・凸に区画された空間
- 与えられた点集合から、凸包をどういう形で決めるか(凸包を構成する点集合か、面集合か…など、どのような表現を取り出すのか)ということも、テーマになる
- Halfspace intersectionと密接な関係にある
- ボロノイ・ドロネー
- ボロノイとドロネーは双対の関係
- ボロノイとドロネーは次元を1つ上げると、それぞれhalfspace intersectionと凸包とに対応づく(Plucker coordinatesに似ている?)
- 2次元はうまく行く、3次元もまあまあ、より高次元は次元を上げて凸包・halfspace intersectionにしてやる方法が中心(だが大変)
- 点間等距離線を引くのがボロノイなので、距離の定義が変わると出来上がりも変わる
- 配置
- 三角化とメッシュ生成
- ドロネーとそれ以外の三角化
- 高次元
- 多角形
- 最短パス・ネットワーク
- 「見える」こと
- Geometric reconstruction
- 曲線・曲面再構成
- 凸・トポロジー・代数:計算機の立場から