駆け足で読む計算幾何学入門 第４章 ボロノイ図

• Wikipediaの記事
• ボロノイ図とは
  • 自然現象に頻発し、既存の自然科学・社会科学ですでに利用されている
  • 数学の対象であり、既存の幾何構造の理論などを利用可能
  • 直接の関連の見出しにくい幾何問題にも応用が利くことが多い
• ボロノイ図の定義と性質
  • 母点
  • ボロノイ領域が平面を分割
    • ボロノイ点とボロノイ辺が分割を構成する
  • ドローネ三角形分割
• 構成法
  • 母点のペアについての評価をするとペア数が多くなると遅いから工夫が必要
    • 逐次添加法
    • Fortuneの走査法
• ドローネ三角形分割
  • 平面上の点集合の三角形分割
    • 点集合による平面分割の一つで、有界な領域のすべてが三角形であるもの
    • 凸包と同様に基本的な幾何構造
  • ドローネ三角形分割はボロノイ図の平面双対
  • ドローネ三角形分割に現れる三角形の内角の最小のものは、すべての三角形分割の中で最大であるなどの特徴を持つ
  • 三角形分割の列挙
  • ドローネ三角形分割を得るアルゴリズム
    • 双対関係にあるボロノイ図を得るアルゴリズムとも言える
    • ボロノイ図よりもドローネ三角形分割の方が得やすいことが多い
• ボロノイ図の拡張
  • 重みつきボロノイ図
  • 多角形内ボロノイ図
  • 高次元ボロノイ図
  • 高次のボロノイ図
  • マンハッタン距離のボロノイ図
  • 最遠点問題を扱うボロノイ図
• 応用
  • 全最近点問題
  • ユークリッド平面上の最小全域木
  • 巡回セールスマン問題
  • 中央軸変換
  • ロボットの動作計画
  • 最大空円
  • 三角形メッシュ