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

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

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



Алгебра и анализ:
Год:
Том:
Выпуск:
Страница:
Найти






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


Алгебра и анализ, 1998, том 10, выпуск 2, страницы 124–147 (Mi aa989)  

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

Статьи

Вычисление пути с минимальным числом звеньев в данном гомотопическом классе между полуалгебраическими препятствиями на плоскости

Д. Ю. Григорьевab, А. О. Слисенкоcd

a Department of Computer Science, Penn State University, University, PA
b С.-Петербургское отделение Математического института им. В. А. Стеклова РАН, Санкт-Петербург
c Институт Информатики РАН, Санкт-Петербург
d Department of Informatics, Universite Paris-12, France
Аннотация: Для данного полуалгебраического множества препятствий на плоскости и двух точек в одной и той же компоненте связности дополнения плоскости до препятствий требуется построить ломаную, соединяющую эти две точки и не пересекающую препятствия, с минимальным числом звеньев, а также с минимальным “полным поворотом”, т.е. суммой абсолютных величин углов поворотов последовательных звеньев. Мы описываем алгоритм, который решает эту задачу за “удельное” полиномиальное время, т.е. полиномиальное время для построения одного звена такой минимальной ломаной. В качестве вычислительной модели используется вещественная равнодоступная адресная машина с вычислением корней (ВРАМ), представляющая собой расширение машины Блюм–Шуба–Смейла. Известно, что количество звеньев в такой минимальной ломаной может быть экспоненциально как функция от длины входных данных или даже от степени многочленов, задающих полуалгебраическое множество препятствий. Фактически описываемый алгоритм строит ломаную с минимальным количеством звеньев и минимальным полным поворотом в данном гомотопическом классе (в дополнении плоскости до препятствий), при условии, что (единственный) кратчайший путь в этом гомотопическом классе не имеет самопересечений. При этом важным является предложенный здесь быстрый алгоритм распознавания принадлежности двух путей одному гомотопическому классу. Ранее в статье Хайнца–Крик–Слисенко–Солерно было показано, что в рассматриваемой ситуации кратчайший путь является полуалгебраической кривой и его можно найти за полиномиальное время на ВРАМ, кроме того, можно построить путь, длина которого приближает длину минимального пути с заданной точностью, за полиномиальное время на обычной (битовой) РАМ.
Ключевые слова: путь с минимальным числом звеньев, алгоритмическое представление гомотопического класса, полуалгебраические препятствия на плоскости, алгоритм полиномиальной сложности.
Поступила в редакцию: 26.03.1997
Реферативные базы данных:
Тип публикации: Статья
Образец цитирования: Д. Ю. Григорьев, А. О. Слисенко, “Вычисление пути с минимальным числом звеньев в данном гомотопическом классе между полуалгебраическими препятствиями на плоскости”, Алгебра и анализ, 10:2 (1998), 124–147; St. Petersburg Math. J., 10:2 (1999), 315–332
Цитирование в формате AMSBIB
\RBibitem{GriSli98}
\by Д.~Ю.~Григорьев, А.~О.~Слисенко
\paper Вычисление пути с~минимальным числом звеньев в~данном гомотопическом классе между полуалгебраическими препятствиями на плоскости
\jour Алгебра и анализ
\yr 1998
\vol 10
\issue 2
\pages 124--147
\mathnet{http://mi.mathnet.ru/aa989}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=1629395}
\zmath{https://zbmath.org/?q=an:0945.68534}
\transl
\jour St. Petersburg Math. J.
\yr 1999
\vol 10
\issue 2
\pages 315--332
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/aa989
  • https://www.mathnet.ru/rus/aa/v10/i2/p124
  • Эта публикация цитируется в следующих 2 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Алгебра и анализ St. Petersburg Mathematical Journal
    Статистика просмотров:
    Страница аннотации:418
    PDF полного текста:390
    Первая страница:1
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024