| Найдено документов - 1 | Статьи из номера журнала: ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА. Т. 13, № 2. - Москва : Открытые системы, 2007. - Текст : электронный. | Версия для печати |
Сортировать по:
1. Статья из журнала
| Малинаускас, К. К. (Автор МИЭТ). Динамическое построение абстрактных диаграмм Вороного / К. К. Малинаускас. - Текст : электронный // ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА. - Москва : Открытые системы, 2007. - Т. 13, № 2. - С. 133-146. - URL: http://mech.math.msu.su/~fpm/rus/contents.htm (дата обращения: 14.08.2026). - Режим доступа: свободный. | |
| Авторы: | Малинаускас, К. К. |
| Ключевые слова: | Вычислительная геометрия, Абстрактная диаграмма вороного, Динамические алгоритмы |
| Аннотация: | Абстрактная диаграмма Вороного (АДВ), определённая Р.Кляйном, является обобщением разного рода обычных диаграмм Вороного структур данных, активно используемых впоследние десятилетия в науке и на практике для решения геометрических задач. В данной работе представлен полностью динамический алгоритм построения АДВ, основанный на инкрементном алгоритме Р. Кляйна. Временные затраты алгоритма на добавление нового объекта в АДВ с n объектами O(n) вхудшем случае. Впервые доказана возможность эффективного удаления объекта без полного перестроения АДВ. Предложенный для этого способ требует в среднем O(mn) времени, где m число невидимых объектов АДВ. В частности, если невидимые объекты не разрешены, средняя сложность составляет O(n). В любой момент времени алгоритм использует память размера O(n) |
| Поиск: | Источник |
| Электронный документ | Для просмотра необходимо войти в личный кабинет |