駆け足で読む計算幾何学入門 第５章 アレンジメント

• アレンジメントとは
  • ２次元の場合：直線による平面の分割
  • ３次元の場合：平面による空間の分割
  • 分割は、点、辺、セル(いくつかの辺に囲まれる凸領域)などを要素として構成されるが、それらの間の接続関係
• アレンジメントの組合せ特性と構成アルゴリズム
  • 単純・退化
  • アレンジメントは複雑であるので、時間計算量も大きく、記憶領域量も大きくなりうる
  • 平面上の直線のアレンジメントに関する結果を高次元に拡張できるよう、アレンジメント理論は構成されている
• 幾何変換
  • 双対性
    • 双対変換は幾何変換のひとつ
    • 高次元におけるボロノイ図と凸包
    • 高次のボロノイ図とアレンジメント
• 関数族のエンベロープとDavenport-Schinzel列
  • 曲線・曲面への拡張
    • ２線分の交差を「ある線分がもうひとつの線分を分離するかどうか」で判定すると考えると、曲線・曲面への拡張は、分離の定義をすげかえることである
• 応用
  • ユークリッド距離変換
  • 様相グラフ
  • ハムサンドイッチカット
    • どのサンドイッチも同じ量のパン、ハムとチーズの２つの部分に分けられるという定理のこと(ハムサンドイッチ定理)。この定理を２次元の離散問題にすると、任意の点集合をそれぞれ二等分する直線が必ず存在するということになる。２つの点集合がある直線によって完全に分離されるとき、アレンジメントを用いることで、その直線を線形時間で見つけることができるという。