ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
2007, ТОМ 13, ВЫПУСК 2, СТР. 133-146

Динамическое построение абстрактных диаграмм Вороного

К. К. Малинаускас

Аннотация

Посмотреть как HTML    Посмотреть как рисунок

Абстрактная диаграмма Вороного (АДВ), определённая Р. Кляйном, является обобщением разного рода обычных диаграмм Вороного -- структур данных, активно используемых в последние десятилетия в науке и на практике для решения геометрических задач. В данной работе представлен полностью динамический алгоритм построения АДВ, основанный на инкрементном алгоритме Р. Кляйна. Временные затраты алгоритма на добавление нового объекта в АДВ с $n$ объектами -- $O(n)$ в худшем случае. Впервые доказана возможность эффективного удаления объекта без полного перестроения АДВ. Предложенный для этого способ требует в среднем $O(mn)$ времени, где $m$ -- число невидимых объектов АДВ. В частности, если невидимые объекты не разрешены, средняя сложность составляет $O(n)$. В любой момент времени алгоритм использует память размера $O(n)$.

Полнотекстовая версия статьи в формате PDF (567 Kb)

URL страницы: http://mech.math.msu.su/~fpm/rus/k07/k072/k07205h.htm
Изменения вносились 23 мая 2007 г.