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

22

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.ststst

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(nlogn)

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.

Jeffε
źródło
4
byłoby miło, gdyby istniała lista trudnych problemów o sumie kwadratowej.
Suresh Venkat
4
To brzmi jak idealne pytanie do cstheory. Dlaczego o to nie pytasz?
Peter Shor

Odpowiedzi:

4

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?

Elias
źródło
Potrzebujesz 50 punktów reputacji, aby dodać komentarz w stackexchange. Więcej informacji tutaj: cstheory.stackexchange.com/privileges/comment . Ponieważ podajesz jakieś informacje, myślę, że możesz opublikować je jako odpowiedź.
chazisop
1
W „łatwym” przypadku, gdy przeszkodą są punkty, najkrótsza ścieżka euklidesowa (lub bardziej formalnie, ścieżka infimal) jest zawsze odcinkiem linii prostej, a jej obliczenie jest banalne. Ale czy nawet w przypadku najkrótszych ścieżek na płaskich wykresach o długości krawędzi euklidesowej masz odniesienie do twardości sumy pierwiastków? (Nie jest trudno zauważyć redukcję dla wykresów czterowymiarowych, ponieważ każda liczba całkowita jest sumą co najwyżej czterech idealnych kwadratów.)
Jeffε
3
4k+1
Masz rację. „Łatwa” sprawa jest raczej banalna.
Elias