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