Читать онлайн «Кибернетический сборник. Новая серия. Выпуск 27»

Кибернетический сборник НОВАЯ СЕРИЯ ВЫПУСК 27 Перевод с английского под редакцией О. Б. ЛУПАНОВА И О. М. КАСИМ-ЗАДЕ МОСКВА «МИР» 1990 ББК 32. 81 К38 УДК 519. 95 Кибернетический сборник. Новая серия. Вып. 27. Сб. К38 статей: Пер. с англ. — М. : Мир, 1990. — 200 с, ил. ISSN 0234—1921 Продолжение известной серии сборников, начатой издательством в 1965 г. В данном выпуске содержатся оригинальные и обзорные ра- работы зарубежных ученых по актуальным проблемам теоретической ки- кибернетики и ее приложениям. Большой интерес вызовут статьи К. Па- падимитриу и др. о построении геодезических и Р. Тарьяна и др. о сверхбыстрых алгоритмах триангуляции. Применению новых методов перечислительной комбинаторики посвящена статья Ж. Вьенно. Вклю- Включены также работы по теории сложности, алгебраическим схемам отно- отношений и обзор по методам преобразования многоуровневых изображе- изображений в двухуровневые. Среди авторов — специалисты из Канады, США, Франции. Для научных работников, инженеров-исследователей, аспирантов и студентов университетов. Редакция литературы по математическим наукам ISSN 0234—1921 © состав, Лупанов О. Б. , Касим-Заде О. М. ; пе- перевод на русский язык, коллектив переводчи- переводчиков, 1990. Дискретная геодезическая задача0 Джозеф Митчел2), Дэвид Маунт3) и Кристос Пападимитриу4) Предлагается алгоритм определения кратчайшего пути меж- между двумя точками на произвольной (возможно, невыпуклой) мно- многогранной поверхности. Путь должен проходить по поверхно- поверхности; метрика предполагается евклидовой. Сложность алгоритма по времени составляет О (n2 log /г), а по объему памяти О (/г2), где п — число ребер поверхности. После того как алгоритм отработает, расстояние от начальной точки до любой концевой точки поверхности может быть определено с помощью стан- стандартных методов за время О (log/г) локализацией положения конечной точки в полученном разбиении поверхности. Кратчай- Кратчайший путь от начальной до конечной точки может быть найден за время O(& + log/z), где k — число граней, через которые он проходит. Алгоритм можно обобщить на случай нескольких на- начальных точек, что позволяет строить на поверхности диаграм- диаграмму Вороного, при этом п равно максимуму из числа вершин поверхности и числа начальных точек. 1. ВВЕДЕНИЕ Недавние исследования алгоритмических аспектов построе- построения роботов и навигации в средах с препятствиями привели к нескольким интересным вариантам постановки задачи поиска кратчайшего пути. Задача определения кратчайшего пути между двумя точками в трехмерном пространстве при наличии пре- препятствий в виде многогранников оказывается очень сложной, и для ее решения известны лишь чрезвычайно неэффективные *) The Discrete Geodesic Problem. SIAM J. Comput. , vol. 16, No. 4, August 1987. 2) Department of Operations Research, Stanford University arid Hughes Artificial Intelligence Center, Stanford, California 94305. 3) Department of Computer Science, University of Maryland, Baltimore, Maryland 21201. 4) Department of Operations Research and Department of Computer Sci- Science, Stanford University, Stanford, California 94305.