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