Złożoność obliczania najkrótszych ścieżek w płaszczyźnie z wielokątnymi przeszkodami

Załóżmy, że podano kilka rozłącznych wielokąt prosty w samolocie, a dwa punkty i t zewnątrz każdego wielokąta. Problem najkrótszej ścieżki euklidesowej polega na obliczeniu najkrótszej ścieżki euklidesowej od s do t , która nie przecina wnętrza żadnego wielokąta. Dla konkretności załóżmy, że współrzędne s i t oraz współrzędne każdego wierzchołka wielokąta są liczbami całkowitymi.$s$$t$$s$$t$$s$$t$

Czy ten problem można rozwiązać w czasie wielomianowym?

Oczywiście większość geometrów obliczeniowych natychmiast powiedziałaby „tak”: John Hershberger i Subhash Suri opisali algorytm obliczający najkrótsze ścieżki euklidesowe w czasie , a ten czas jest optymalny w algebraicznym modelu drzewa obliczeniowego. Niestety algorytm Hershbergera i Suriego (i prawie wszystkie powiązane algorytmy przed i po) wydaje się wymagać dokładnej prawdziwej arytmetyki w następującym silnym znaczeniu.$O(n\log n)$

Zadzwoń wielokątny ścieżkę ważna , jeżeli wszyscy jej wnętrze wierzchołki są wierzchołki przeszkód; każda najkrótsza ścieżka euklidesowa jest ważna. Długość dowolnej prawidłowej ścieżki jest sumą pierwiastków kwadratowych liczb całkowitych. Zatem porównanie długości dwóch prawidłowych ścieżek wymaga porównania dwóch sum pierwiastków kwadratowych, czego nie wiemy, jak to zrobić w czasie wielomianowym .

Co więcej, wydaje się całkowicie prawdopodobne, że dowolne wystąpienie problemu sumy pierwiastków kwadratowych można by zredukować do równoważnego problemu najkrótszej ścieżki euklidesowej.

A zatem: Czy istnieje algorytm obliczający czas wielomianowy do obliczania najkrótszych ścieżek euklidesowych? Czy problem NP jest trudny? A może suma pierwiastków kwadratowych ? Albo coś innego?

Kilka uwag:

• Najkrótsze ścieżki wewnątrz (lub na zewnątrz) jednego wielokąta można obliczyć w czasie bez żadnych dziwnych problemów numerycznych przy użyciu standardowego algorytmu lejka, przynajmniej jeśli podano triangulację wielokąta.$O(n)$

• W praktyce arytmetyka zmiennoprzecinkowa jest wystarczająca do obliczenia ścieżek od najkrótszych do precyzji zmiennoprzecinkowej. Interesuje mnie tylko złożoność konkretnego problemu.

• John Canny i John Reif udowodnili, że odpowiedni problem w 3-przestrzeni jest trudny do NP (moralnie, ponieważ może istnieć wykładnicza liczba najkrótszych ścieżek). Joonsoo Choi, Jürgen Sellen i Chee-Keng Yap opisali schemat aproksymacji czasu wielomianowego.

• Simon Kahan i Jack Snoeyink rozważali podobne problemy związane z problemem minimalnej ścieżki łącza w prostym wielokącie.

Może coś mi umknęło, ale jeśli weźmiemy pod uwagę „łatwy” przypadek, w którym wszystkie przeszkody są punktami, mamy problem z obliczeniem najkrótszej ścieżki między dwoma wierzchołkami na wykresie planarnym, co, jeśli się nie mylę, jest znane jako sumy pierwiastków kwadratowych twardych.

PS. Chciałem dodać komentarz, a nie odpowiedź, ale nie mogę znaleźć sposobu. Przepraszam za to. Czy administratorzy mogą mi w tym pomóc?