ボロノイ図を使った最近傍探索

Question

フォーチュンの手法を使って2次元でボロノイ図を生成する方法をうまく実装しました。しかし、今私は点（これは、図を生成するために使用された元の点の一つではありません）のための最近傍のクエリに使用しようとしています。私は人々がO（lg n）時間（そして私はそれらを信じる）で行うことができると言い続けているが、実際にどのように行われたのかの説明は見つけることができない。

私はバイナリ検索に精通していますが、その上限を保証する良い基準がわかりません。また、図をポイントに挿入して周囲のセルを更新する必要があるかもしれないと思ったかもしれませんが、それを行う良い方法を考える（または見つける）ことはできません。

誰かが私を手がかりにすることができますか、より詳しい説明が記載された場所を指し示すことはできますか？

Answer 1

Kirkpatrick's point location data structureのように、ある種の検索構造を平面細分（ボロノイ図）から作成する必要があると思います。