Быстрый способ вычислить диаграмму Вороного, зная k-ближайших соседей

Я знаю, что относительно легко вычислить наборы k-ближайших соседей из мозаики Вороного. А обратная задача? У меня уже есть набор k-ближайших соседей (в 3D), и я хотел бы вычислить объемы и центры ячеек Вороного. Интуитивно должен существовать алгоритм O(n), который делает это, верно?

Кто-нибудь видел что-то подобное реализованным где-нибудь?

заранее спасибо

PS: я предполагаю, что ни одна ячейка Вороного не имеет более k ребер (это предварительное знание о расположении точек, вероятно, позволяет вычислить диаграмму за O (n) независимо от размерности).

PPS: Далее я предполагаю, что для данной точки вершины ячейки Вороного принадлежат множеству kNN (см. комментарии ниже).


algorithm nearest-neighbor voronoi diagram delaunay
person calys    schedule 02.11.2011    source источник
comment
Что делать, если в ячейке Вороного больше k ребер?   -  person Rob Neuhaus    schedule 02.11.2011
comment
@rrenaud: хорошая мысль. На самом деле я ищу эффективный алгоритм, который построил бы ячейку Вороного, если это возможно, и вернул бы исключение, если это не так (в этом случае я создам дополнительную соседнюю точку и начну снова - это часть итеративного схема адаптации для численной аппроксимации дифференциальных уравнений).   -  person calys    schedule 03.11.2011
comment
Если вы работаете в плоскости, то для построения диаграмм Вороного существует алгоритм O(n log n), не нужно иметь дело с kNN.   -  person n. 1.8e9-where's-my-share m.    schedule 03.11.2011
comment
@н.м. Спасибо, это будет алгоритм Fortune, верно? Однако я хотел бы, чтобы этот метод работал в 3D. Я не знаю никакого алгоритма для получения диаграммы Вороного менее чем за O (N ^ 2) в этом случае, поэтому я думал об использовании KNN (который у меня уже есть).   -  person calys    schedule 03.11.2011

Ответы (2)


arrow_upward
1
arrow_downward

Вы можете построить VD следующим образом. Точка P и один из ее k ближайших соседей Q определяют полуплоскость H(P,Q), равноудаленную от P и Q, и полупространство H+(P,Q) с границей H, содержащее P. Тогда ячейка P является пересечением H+(P,Q) для всех Q из k ближайших соседей P. Построение этого пересечения очень тесно связано с проблемой перечисления вершин: http://en.wikipedia.org/wiki/Vertex_enumeration_problem

Вам нужно иметь достаточное количество соседей, чтобы быть уверенным, что построен правильный VD, и я не уверен, что ваши предположения гарантируют это. Надежно только то, что реальная ячейка Вороного точки P входит в ячейку, которую строит приведенный выше алгоритм.

person Samuel Hornus    schedule 03.11.2011
comment
Спасибо! Это была бы идеальная формулировка того, что должен делать алгоритм. Однако я все еще ищу эффективную реализацию. - person calys; 03.11.2011

arrow_upward
0
arrow_downward

Хотя должен быть интуитивно понятный алгоритм, я не думаю, что он действительно существует. Хотя у меня нет формального доказательства (и я не могу его так быстро составить), рассмотрим следующий аргумент:

Рассмотрим случай, когда k-ближайшие соседние точки K точки P находятся по одну сторону от P, т. е. существует плоскость, проходящая через P, такая, что все точки в K находятся по одну сторону от плоскости. Тогда граница ячейки Вороного матрицы P никак не может быть вычислена по точкам из K. Этот аргумент верен для любого k, и я не вижу никакого способа, как алгоритм мог бы обнаружить наличие какой-либо точки на другую сторону P с помощью анализа ближайших соседей. Поэтому я утверждаю, что диаграмма Вороного содержит больше информации, чем статистика k-ближайших соседей, и поэтому преобразование от Вороного к kNN является необратимой редукцией.

С другой стороны, Хьюго Леду разработал алгоритм логарифмического усреднения для воронизации. , вы можете рассмотреть это решение.

Изменить: мой аргумент, вероятно, все еще слишком сложен. Простая мысль о kNN: рассмотрим кластер из k точек, которые являются kNN друг для друга. Подграф kNN для этих точек не связан со всеми остальными точками, что делает невозможным построение диаграммы Вороного. Или, другими словами, диаграмма Вороного содержит k ближайших соседей для любого k, поэтому не может быть восстановлена ​​из любого конечного k.

person thiton    schedule 03.11.2011
comment
да, я полностью согласен. Диаграмма Вороного содержит больше информации, чем kNN, и ее в принципе нельзя восстановить по одному конкретному kNN. Однако меня интересуют только случаи, когда набор точек хороший (т. Е. Вершины ячеек Вороного находятся среди уже имеющихся у нас kNN — для случаев, когда это не так, я хочу перехватить это исключение, добавить новые точки и повторите попытку). Большое спасибо за ссылку на работу Леду. Выглядит очень хорошо, а я и не знал об этом. - person calys; 03.11.2011
comment
@calys: построение диаграммы Вороного для хорошо работающих ячеек kNN тривиально: постройте биссектрису, перпендикулярную линии между каждой точкой и ее соседом, а затем вычислите многоугольник, ограниченный этими линиями. Я просто не думаю, что можно эффективно обнаружить, где эта схема не удалась. Однако дешево проверить, что это не удалось (площадь ячеек Вороного == площади ограничивающего прямоугольника). - person thiton; 03.11.2011
comment
Спасибо. Действительно, это похоже на то, что я хочу сделать. Я надеялся найти где-нибудь эффективную реализацию этого, сделанную кем-то с лучшими навыками программирования, чем я... Что касается проверки того, что схема удалась, я наложу, что все вершины Вороного находятся в радиусе R/2, где R — расстояние до самого дальнего kNN. Это только достаточное условие, но его легко наложить и легко проверить. - person calys; 03.11.2011
comment
Взгляните на библиотеку geogram. Он может вычислять отдельные ячейки Вороного и делает это точно. - person Samuel Hornus; 02.08.2018