点位置決定問題

• ポリゴンで分割された2次元平面があります
  • ポリゴンは互いに重ならない、どのポリゴンにも属さないエリアは無い
• 平面にある点が落とされました
• 落ちたのはどのポリゴンですか？

を、高速に求めましょうという問題。

《木》 - ORWiki

• 1ポリゴンずつ内外判定を行う

ポリゴン数をN、1ポリゴン当たりの平均辺数をMとしたとき、$O(NM)$になる。
N=10000、M=100くらいならやってやれなくは無い。

• ポリゴンごとに、自身をぴったり覆う矩形（辺はXY軸に平行）を事前計算
  • 点がその矩形に入っていないなら、当然ポリゴンにも入っていない
• まず矩形との内外判定を行う。これは単なる数値比較で済む
• 矩形に入っていたらポリゴンの内外判定を行う

最悪オーダーは$O(NM)$のままだが、定数倍がかなり減る

• Spaghetti Source - 点位置決定 (スラブ地図)
• 全てのポリゴン頂点を、x軸順にソートしておく
  • 点がどの頂点の間に位置するかは、二分探索で得られる
• 

• 計算量
  • 頂点数をPとしたとき、
    • 事前計算時間$O(P^2)$
    • 事前計算空間量$O(P^2)$
    • クエリ計算時間$O(\log{P})$
  • 総当たりで解けないような規模の問題ならどっちみちこの方法でも現実的にメモリが足りない
  • メモリが豊富に用意でき、クエリの応答時間が非常に大事なシチュエーションでは使える?

N. Sarnak and R.E. Tarjan, “Planar Point Location Using Persistent-Search Trees,” Communications of the ACM, 29 (1986), 669-679.

スラブ法の改良？ 全部を持たず、赤黒木で更新していくらしい。

• 計算量
  • 事前計算時間$O(P \log{P})$
  • 事前計算空間量$O(P)$
  • クエリ計算時間$O(\log{P})$

多分ここに書かれているのもそれっぽい？計算幾何学セミナー 第6章 点位置決定問題（PDF 形式）