Я успешно реализовал способ генерирования диаграмм Вороного в двух измерениях, используя метод Фортуны.Но сейчас я пытаюсь использовать его для запросов ближайшего соседа для точки (которая не является одной из исходных точек, используемых для создания диаграммы).Я продолжаю видеть, как люди говорят, что это можно сделать за O (LG N) время (и я им верю), но я не могу найти описание того, как это на самом деле делается.
Я знаком с бинарнымпоиски, но я не могу найти хорошие критерии, чтобы гарантировать эту верхнюю границу.Я также подумал, что это может быть связано с вставкой точки в диаграмму и обновлением окружающих ячеек, но я не могу придумать (или найти) хороший способ сделать это.
Может кто-нибудь подсказать мне,или указать место с более подробным описанием?