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