#algorithm #diagram #nearest-neighbor #delaunay #voronoi
#алгоритм #диаграмма #ближайший сосед #делоне #вороной
Вопрос:
Я знаю, что относительно легко вычислить наборы k ближайших соседей из мозаики Вороного. Как насчет обратной проблемы? У меня уже есть набор k ближайших соседей (в 3D), и я хотел бы вычислить объемы и центры ячеек Вороного. Интуитивно, должен быть алгоритм O (n), который делает это, верно?
Кто-нибудь видел что-то подобное, реализованное где-нибудь?
Заранее спасибо
PS: Я предполагаю, что ни одна ячейка Вороного не имеет более k ребер (это предварительное знание о расположении точек, вероятно, позволяет вычислить диаграмму в O (n) независимо от размерности).
Далее я предполагаю, что для данной точки вершины ячейки Вороного принадлежат множеству kNN (см. Комментарии ниже).
Комментарии:
1. Что, если ячейка Вороного имеет более k ребер?
2. @rrenaud: хорошая мысль. На самом деле я ищу эффективный алгоритм, который построил бы ячейку Вороного, если это возможно, и вернул бы исключение, если это не так (в этом случае я сгенерирую дополнительную соседнюю точку и начну снова — это часть итерационной схемы адаптации для численной аппроксимации дифференциальных уравнений).
3. Если вы работаете в плоскости, то для построения диаграмм Вороного существует алгоритм O (n log n), нет необходимости иметь дело с kNN.
4. @n.m. Спасибо, это был бы алгоритм Фортуны, верно? Я бы хотел, чтобы этот метод работал в 3D. Я не знаю ни одного алгоритма для получения диаграммы Вороного менее чем за O (N ^ 2) в этом случае, поэтому я думал об использовании KNN (который у меня уже есть).
Ответ №1:
Вы можете построить 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 включена в ячейку, которую создает приведенный выше алгоритм.
Комментарии:
1. Спасибо! Это была бы идеальная формулировка того, что должен делать алгоритм. Тем не менее, я все еще ищу эффективную реализацию.
Ответ №2:
Хотя должен быть интуитивно понятный алгоритм, я не думаю, что он действительно существует. Хотя у меня нет формального доказательства (и я не мог его составить так быстро), рассмотрим следующий аргумент:
Рассмотрим случай, когда k ближайших соседних точек K точки P находятся по одну сторону от P, т. Е. Существует плоскость, проходящая через P, такая, что все точки в K находятся на одной стороне плоскости. Тогда граница ячейки Вороного из P не может быть вычислена каким-либо образом из точек в K. Этот аргумент справедлив для любого k, и я не вижу никакого способа, как алгоритм может обнаружить наличие какой-либо точки на другой стороне P с помощью анализа ближайших соседей. Поэтому я утверждаю, что диаграмма Вороного содержит больше информации, чем статистика k ближайших соседей, и поэтому преобразование из Voronoi в kNN является необратимым сокращением.
С другой стороны, Хьюго Леду разработал алгоритм n log n среднего случая для вороноизации, вы можете рассмотреть это решение.
Редактировать: мой аргумент, вероятно, все еще слишком сложен. Простая мысль о kNN: рассмотрим кластер из k точек, которые являются kNN друг для друга. Подграф kNN для этих точек отключен от всех других точек, что делает построение диаграммы Вороного невозможным. Или, другими словами, диаграмма Вороного содержит k ближайших соседей для любого k, поэтому не может быть восстановлена из любого конечного k.
Комментарии:
1. да, я полностью согласен. Диаграмма Вороного содержит больше информации, чем kNN, и ее в принципе нельзя восстановить из одного конкретного kNN. Однако меня интересуют только случаи, когда набор точек «хороший» (т. Е. Вершины ячеек Вороного входят в число kNN, которые у нас уже есть — для случаев, когда это неверно, я хочу перехватить это исключение, добавить новые точки и повторить попытку). Большое спасибо за ссылку на работу Леду. Это выглядит очень хорошо, и я не знал об этом.
2. @calys: Построение диаграммы Вороного для хорошо управляемых ячеек kNN тривиально: постройте перпендикулярную биссектрису прямой между каждой точкой и ее соседом, а затем вычислите многоугольник, ограниченный этими линиями. Я просто не думаю, что можно эффективно определить, где эта схема не удалась. Однако дешево проверить, что это не удалось (площадь ячеек Вороного == площадь охватывающего прямоугольника).
3. Спасибо. Действительно, это похоже на то, что я хочу сделать. Я надеялся найти эффективную реализацию этого где-нибудь, сделанную кем-то с лучшими навыками программирования, чем у меня… Что касается проверки того, что схема выполнена успешно, я наложу, что все вершины Вороного находятся в радиусе R / 2, где R — расстояние до самого дальнего kNN. Это только достаточное условие, но его легко наложить и легко проверить.
4. Взгляните на библиотеку geogram. Он может вычислить одну ячейку Вороного и делает это точно.