幾何的データ構造と探索 ぱらぱらめくる『Handbook of Discrete and Computational Geometry』

• 点の位置
  • 幾何オブジェクトが置かれた空間に、点を与えたときに、その点がオブジェクトについてどのような相対的な位置にあるかの判定"point-location problem"
  • １次元空間の場合でも、いくつかのアルゴリズムが記載されている
  • ２次元空間の多面体の内外判定 "point-in-polygon"：点から始まる直線と多面体を構成する辺との交差回数で判定
  • Planar point location: 交差することなくうまく置くことが"planar",平面グラフ、とか
    • Static methods, Dynamic methods
      • ２次元平面探索を木探索に変換
      • 探索空間を木化した上で、探索しながらその探索路を改変するのがdynamic methods
  • ３次元以上に上がると平面グラフも使えず難しくなる
• 衝突・近接
  • 色々な提案がなされている
  • 衝突を検出
  • 隔てる距離を見つける。多面体と多面体の間隙
• 範囲探索
  • 空間にある部分空間が定まっていて、また点の集合も定まっているときに、繰り返して点と部分空間との位置関係を問い合わせたい。１度の問い合わせでなく、繰り返すなら、情報を蓄積して、より高速に回答できるようにしたい
• Ray shooting、空間における直線
  • 3D空間の直線をPlucker coordinatesで表す。４次元同次座標で表して、外積代数によって幾何的オブジェクトを表す
  • Ray shooting はある点からある方向に進んだときに、多面体のどこを通るか、という問題
• 幾何的交叉
• Nearest-neighbors
  • 高次元の場合は、真の解を得るのが困難なので、近似解を探す
  • 最近点はわからないけれど、それがあったとして、その最近距離よりある程度までの距離を許容し、その許容範囲にある点を「最近点」の近似解とする、という方法