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

Для данного полуалгебраического множества препятствий на плоскости и двух точек в одной и той же компоненте связности дополнения плоскости до препятствий требуется построить ломаную, соединяющую эти две точки и не пересекающую препятствия, с минимальным числом звеньев, а также с минимальным “полным поворотом”, т.е. суммой абсолютных величин углов поворотов последовательных звеньев. Мы описываем алгоритм, который решает эту задачу за “удельное” полиномиальное время, т.е. полиномиальное время для построения одного звена такой минимальной ломаной. В качестве вычислительной модели используется вещественная равнодоступная адресная машина с вычислением корней (ВРАМ), представляющая собой расширение машины Блюм–Шуба–Смейла. Известно, что количество звеньев в такой минимальной ломаной может быть экспоненциально как функция от длины входных данных или даже от степени многочленов, задающих полуалгебраическое множество препятствий. Фактически описываемый алгоритм строит ломаную с минимальным количеством звеньев и минимальным полным поворотом в данном гомотопическом классе (в дополнении плоскости до препятствий), при условии, что (единственный) кратчайший путь в этом гомотопическом классе не имеет самопересечений. При этом важным является предложенный здесь быстрый алгоритм распознавания принадлежности двух путей одному гомотопическому классу. Ранее в статье Хайнца–Крик–Слисенко–Солерно было показано, что в рассматриваемой ситуации кратчайший путь является полуалгебраической кривой и его можно найти за полиномиальное время на ВРАМ, кроме того, можно построить путь, длина которого приближает длину минимального пути с заданной точностью, за полиномиальное время на обычной (битовой) РАМ.