ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
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 г.