Fortuneの方法を使用して、2次元でボロノイ図を生成する方法を正常に実装しました。しかし今、私はそれをポイントの最近傍クエリに使用しようとしています（これはダイアグラムの生成に使用された元のポイントの1つではありません）。私はそれがO（lg n）時間でできると人々が言っているのを見続けています（そして私は彼らを信じています）が、それが実際にどのように行われたかについての説明を見つけることができません。
私は二分探索に精通していますが、その上限を保証するための適切な基準を理解することはできません。また、図にポイントを挿入して周囲のセルを更新することと関係があるかもしれないと考えましたが、それを行うための良い方法を考える（または見つける）ことはできません。
誰かが私を手がかりにしたり、より詳細な説明のある場所を指し示したりできますか？