Аппроксимация диаграммы вороного k-го порядка

Представлен алгоритм построения обобщенной дискретной диаграммы Вороного k-го порядка на сетке с переменным шагом, основанный на идее рекурсивного разбиения пространства. В алгоритме в качестве структуры данных используется дерево разбиения пространства (2d-дерево), также известное как квадродерево и октодерево для 2-х и 3-х мерных пространств. Алгоритм рекурсивно уточняет границы ячеек Вороного (би-секторы), используя только локальные свойства в каждой точке области построения. В результате вычисления сосредотачиваются в области границ ячеек (глубина 2d-дерева больше в области границ ячеек), и достигается существенный выигрыш производительности по сравнению с наивным алгоритмом (полным перебором). Алгоритм позволяет обобщать форму сайтов, используемую метрику, порядок диаграммы и число измерений.