RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Фундамент. и прикл. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Фундамент. и прикл. матем., 2007, том 13, выпуск 2, страницы 133–146 (Mi fpm20)  

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

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

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

Московский государственный институт электронной техники (технический университет)

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

Ключевые слова: вычислительная геометрия, абстрактная диаграмма Вороного, динамические алгоритмы.

Полный текст: PDF файл (566 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Journal of Mathematical Sciences (New York), 2008, 154:2, 214–222

Реферативные базы данных:

УДК: 514, 519.6

Образец цитирования: К. К. Малинаускас, “Динамическое построение абстрактных диаграмм Вороного”, Фундамент. и прикл. матем., 13:2 (2007), 133–146; J. Math. Sci., 154:2 (2008), 214–222

Цитирование в формате AMSBIB
\RBibitem{Mal07}
\by К.~К.~Малинаускас
\paper Динамическое построение абстрактных диаграмм Вороного
\jour Фундамент. и прикл. матем.
\yr 2007
\vol 13
\issue 2
\pages 133--146
\mathnet{http://mi.mathnet.ru/fpm20}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2322975}
\zmath{https://zbmath.org/?q=an:1157.68069}
\transl
\jour J. Math. Sci.
\yr 2008
\vol 154
\issue 2
\pages 214--222
\crossref{https://doi.org/10.1007/s10958-008-9160-x}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-54249164924}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/fpm20
  • http://mi.mathnet.ru/rus/fpm/v13/i2/p133

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Klein R., Langetepe E., Nilforoushan Z., “Abstract Voronoi diagrams revisited”, Comput. Geom., 42:9 (2009), 885–902  crossref  mathscinet  zmath  isi
  • Фундаментальная и прикладная математика
    Просмотров:
    Эта страница:785
    Полный текст:179
    Литература:47
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020