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

Question

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

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

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

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

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

Answer 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 включена в ячейку, которую строит алгоритм выше.

Answer 2

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

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

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

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