Сложность вычисления кратчайших путей на плоскости с полигональными препятствиями

22

Предположим, нам дано несколько непересекающихся простых многоугольников на плоскости и две точки и t вне каждого многоугольника. Задача евклидова кратчайшего пути состоит в том, чтобы вычислить евклидов кратчайший путь от s до t , который не пересекает внутреннюю часть любого многоугольника. Для конкретности предположим, что координаты s и t и координаты каждой вершины многоугольника являются целыми числами.ststst

Можно ли решить эту проблему за полиномиальное время?

Конечно, большинство вычислительных геометров сразу скажут «да»: Джон Хершбергер и Субхаш Сури описали алгоритм, который вычисляет евклидовы кратчайшие пути за время , и эта временная граница является оптимальной в алгебраической модели вычислительного дерева. К сожалению, алгоритм Хершбергера и Сури (и почти все связанные алгоритмы до и с тех пор), кажется, требуют точной реальной арифметики в следующем сильном смысле.O(nlogn)

Назовите полигональный путь действительным, если все его внутренние вершины являются вершинами препятствий; каждый евклидов кратчайший путь действителен. Длина любого допустимого пути является суммой квадратных корней целых чисел. Таким образом, сравнение длин двух допустимых путей требует сравнения двух сумм квадратных корней, что мы не знаем, как сделать за полиномиальное время .

Более того, кажется вполне правдоподобным, что произвольный случай проблемы суммы квадратных корней может быть сведен к эквивалентной евклидовой задаче кратчайшего пути.

Итак: существует ли алгоритм полиномиального времени для вычисления евклидовых кратчайших путей? Или проблема NP-сложная? Или сумма квадратных корней трудно ? Или что-то другое?

Несколько заметок:

  • Кратчайшие пути внутри (или снаружи) одного многоугольника могут быть вычислены за раз без каких-либо странных численных проблем с использованием стандартного алгоритма воронки, по крайней мере, если дана триангуляция многоугольника.O(n)

  • На практике арифметика с плавающей запятой достаточна для вычисления путей, кратчайших до точности с плавающей запятой. Меня интересует только сложность точной проблемы.

  • Джон Кэнни и Джон Рейф доказали, что соответствующая задача в 3-пространстве NP-трудна (морально, потому что может быть экспоненциальное число кратчайших путей). Joonsoo Choi, Jürgen Sellen и Chee-Keng Yap описали схему аппроксимации за полиномиальное время.

  • Саймон Кахан и Джек Сноейнк рассмотрели аналогичные вопросы для связанной проблемы путей минимальной связи в простом многоугольнике.

Jeffε
источник
4
было бы неплохо, если бы существовал список трудных задач с суммой квадратов корней.
Суреш Венкат
4
Это звучит как идеальный вопрос для теории. Почему бы тебе не спросить это?
Питер Шор

Ответы:

4

Может быть, я что-то упускаю, но если мы рассмотрим «легкий» случай, когда все препятствия являются точками, то у нас возникает проблема вычисления кратчайшего пути между двумя вершинами в плоском графе, который, если я не ошибаюсь, известен как суммы квадратных корней трудно.

PS. Я хотел добавить комментарий, а не ответ, но не могу найти как. Я прошу прощения за то. Могут ли админы помочь мне с этим.

Элиас
источник
Вам нужно 50 репутации, чтобы оставить комментарий в stackexchange. Более подробная информация здесь: cstheory.stackexchange.com/privileges/comment . Так как вы предоставляете некоторую информацию, я думаю, можно опубликовать ее в качестве ответа.
chazisop
1
В «простом» случае, когда препятствиями являются точки, евклидов кратчайший путь (или, более формально, бесконечный путь) всегда является отрезком прямой, и вычисление его тривиально. Но даже для кратчайших путей в плоских графах с евклидовой длиной ребра, есть ли у вас ссылка на твердость суммы корней? (Нетрудно увидеть сокращение для четырехмерных графиков, потому что каждое целое число является суммой не более четырех совершенных квадратов.)
Джефф
3
4k+1
Вы правы. «Легкий» случай довольно тривиален.
Элиас