駆け足で読む計算幾何学入門 第３章 凸包の計算

• 凸包のアルゴリズムの出力
  • 凸包を構成する点集合の決定
  • 凸包構成点の周回順序の決定
• 包装法
  • 確定した凸包構成点から次を探す
• Grahamの走査法
  • ある点からの偏角による位置の評価とソート
• 逐次構成法
  • 部分データでの解を求め、データを加えながら、解を変更していく
• 分割統治法
• 分割統治法と縮小法の組合せ
  • 冗長要素の除去を取り入れる
• 高次元の点集合の凸法への拡張
• 応用
  • 障害物回避
  • 最小面積ボックス
  • クラスタリング