Как запросить диаграмму Вороного?

Question

Я использую boost для вычисления диаграммы Вороного для набора точек в 2-D, очень просто;

std::vector<Point> points;
...
voronoi_diagram<double> vd;
construct_voronoi(points.begin(), points.end(), &vd);

Есть ли алгоритм для обработки полученных многоугольников, чтобы запрос «К какому сайту принадлежит данная точка?» можно ответить в постоянное время? Другими словами, в каком многоугольнике данная точка расположена среди набора многоугольников?

Конечно, можно вычислить и сравнить расстояние от данной точки до существующих, но это займет время O (n) и не использует информацию, закодированную в диаграмме Вороного.

Answer 1

На вопрос «К какому сайту принадлежит данная точка?» это просто еще один способ сформулировать задачу поиск ближайшего соседа : соответствующий многоугольник Вороного связан с ближайшей точкой в ​​наборе, генерирующем диаграмму Вороного. К сожалению,

• не существует алгоритма с постоянным временем для решения этой проблемы, а
• диаграмма Вороного не обеспечивает решения проблемы быстрее, чем поиск O (N) .

Если вам нужно найти много точек на диаграмме Вороного, вы можете построить дерево поиска и обычно получить производительность O (log N). Ответ на этот вопрос делает это в python построении дерева kd для выполнения запроса. В ускорении вы можете использовать для этой цели существующее R-дерево .

Существует способ построить дерево поиска на основе диаграмм Вороного ( иерархия Делоне ). Возможно, это даст некоторые незначительные преимущества , если вы также будете использовать его для построения диаграммы Вороного. Но не существует легко доступных оптимизированных библиотек, как для общей задачи поиска c.