|
Эта публикация цитируется в 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
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/aa989 https://www.mathnet.ru/rus/aa/v10/i2/p124
|
Статистика просмотров: |
Страница аннотации: | 418 | PDF полного текста: | 390 | Первая страница: | 1 |
|