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

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