Каков наиболее эффективный алгоритм вычисления границы ячейки Вороного? Чтобы быть более конкретным, скажем, у нас есть список точек (в 2 измерениях для упрощения задачи): P1, P2, P3.. Pn Теперь, если я хочу просто найти длину границы ячейки Вороного случайной точки , скажем, Pi, которая является общей с другой соседней точкой Pj, существует ли для этого эффективный алгоритм?
Спасибо!
Теперь у меня есть решение этой проблемы, но я не уверен, достаточно ли оно эффективно для многих измерений. Позвольте мне переформулировать проблему.
Проблема: скажем, наш список точек {P1, P2, P3, . . .Pk, X} и наша точка запроса — X; т. е. нас интересует нахождение гиперобъема грани, которая является общей (в 2-х измерениях длиной общего ребра) между ячейкой Вороного Pi и ячейкой Вороного X.
Решение:
Находим множество точек CC = {T1, T2, T3, . . .Tk-1}, которые являются центрами описанных окружностей точек {Pi,X,Pj}, где j‹>i и 1‹=j‹=k. Это можно сделать за O(k)
Из множества CC можно удалить точки, не лежащие в ячейке Вороного X. Это можно сделать за O(k^2) и без вычисления какой-либо диаграммы Вороного.
Остальные точки, оставшиеся в наборе CC, будут полностью определять ограничивающую грань, которая является общей для ячейки Вороного Pi и ячейки Вороного X. В двух измерениях у нас останется только две точки (конечные точки общего ребра) в множестве CC, из которого легко найти длину.
Теперь, когда мы определили нашу ограничивающую грань, мы можем легко найти приблизительный объем этой грани за полиномиальное время.
O(NlogN), а затем легко вычислить список длин. Вам нужен алгоритм с меньшей сложностью или что-то еще? - person Skyler schedule 23.12.2013