Problemy geometryczne, które są NP kompletne w

37

Szereg problemów geometrycznych jest łatwych, gdy rozważa się je w , ale są NP-kompletne w R d dla d 2 (w tym jeden z moich ulubionych problemów, pokrywa dysku jednostki).R1Rdd2

Czy ktoś wie o problemie, który jest polytime rozwiązywalne dla i R 2 , ale NP-zupełny dla R d , d 3 ? R1R2Rd,d3

Mówiąc bardziej ogólnie, czy istnieją problemy, które są NP-zupełny dla ale polytime rozwiązywalne dla R k - 1 , gdzie k 3 ?RkRk1k3

Bob Fraser
źródło
Czy dopasowanie trójwymiarowe jest geometryczne?
Jukka Suomela,
1
nie całkiem. „trójwymiarowy” jest kartezjański, a nie euklidesowy.
Suresh Venkat

Odpowiedzi:

25

Ustaw osłonę na pół spacji.

Biorąc pod uwagę zestaw punktów w płaszczyźnie i zestaw półpłaszczyzn obliczający minimalną liczbę półpłaszczyzn pokrywających zestawy punktów, można rozwiązać w czasie wielomianowym w płaszczyźnie. Problemem jest jednak NP trudny w 3d (jest trudniejszy niż znalezienie minimalnej osłony według podzbioru dysków punktów w 2d). W 3d otrzymasz podzbiór półprzestrzeni i punktów i szukasz minimalnej liczby półprzestrzeni pokrywających punkty.

Algorytm czasu policy w 2d jest opisany tutaj: http://valis.cs.uiuc.edu/~sariel/papers/08/expand_cover/

Sariel Har-Peled
źródło
Jestem trochę zawstydzony, że nie znałem tego wyniku, biorąc pod uwagę, jak blisko są problemy, nad którymi pracuję :-) To jest dokładnie taka odpowiedź, na którą liczyłem. Kiedy mówisz, że jest trudniejszy niż okładka dysku w 2D, myślę, że masz na myśli, że jest to APX-twardy?
Bob Fraser
1
Problem 2d jest wielomianowy. Drugi to NP-Hard. Jednak nie sądzę, że problem 3D jest trudny w APX. Istnieją dobre powody, by sądzić, że PTAS może być możliwy poprzez wyszukiwanie lokalne ...
Sariel Har-Peled,
... a trudniej miałem na myśli, że problem z dyskiem można podnieść (tj. zmniejszyć) do problemu półprzestrzeni w 3d.
Sariel Har-Peled,
29

Nie jest to dokładnie to, o co pytasz, ponieważ wersja 3d jest jeszcze trudniejsza niż NP-complete, ale: Znalezienie najkrótszej ścieżki między dwoma punktami między wielobocznymi przeszkodami w płaszczyźnie odbywa się w czasie wielomianowym (najprościej, zbuduj wykres widoczności dwóch terminali i wierzchołki wielokąta i zastosuj Dijkstrę; istnieje również bardziej skomplikowany algorytm O (n log n) z powodu Hershbergera i Suri, SIAM J. Comput. 1999), ale znalezienie najkrótszej ścieżki między przeszkodami wielościennymi w 3D jest ukończone w PSPACE (Canny i Reif, FOCS 1987).

David Eppstein
źródło
10
Czy jesteś pewien co do przypadku płaskiego? Algorytmy, które przytaczasz, zasadniczo wymagają dokładnej prawdziwej arytmetyki! cstheory.stackexchange.com/questions/4034/…
Jeffε
Er. Słuszna uwaga. I nie mogę się z tego wydostać, mówiąc, że używam zmiennoprzecinkowego i przybliżonego, ponieważ problem 3d można dobrze oszacować. Ups Wydaje mi się, że istnieje „dokładna prawdziwa arytmetyka”, w której jeden jest wielomianowy, a drugi trudny, ale nadal masz rację, to inny sposób, w jaki nie odpowiada na pytanie.
David Eppstein,
6
To jest naprawdę interesujące. Suma problemu z pierwiastkami kwadratowymi przekształca się w szereg problemów w cg, w których problem byłby łatwy, z wyjątkiem tego szczegółu. Jest w pewien sposób świetny, ponieważ jest to jeden z tych problemów, który trzeba przekonać ludzi, że jest trudny. Dzięki za wskazówki.
Bob Fraser
20

Każdy niewypukły wielokąt w płaszczyźnie może być triangulowany w czasie O (n) bez punktów Steinera; to znaczy każdy wierzchołek triangulacji jest wierzchołkiem wielokąta. Co więcej, każda triangulacja ma dokładnie n-2 trójkątów.

Jednak ustalenie, czy niewypukły wielościan w R ^ 3 może być triangulowany bez punktów Steiner, jest NP-całkowite. Wynik twardości NP zachowuje się nawet wtedy, gdy otrzymasz triangulację z jednym punktem Steiner'a, więc nawet przybliżenie minimalnej liczby wymaganych punktów Steiner jest trudne NP. [Jim Ruppert i Raimund Seidel. O trudnościach triangulacji trójwymiarowej niep wypukłej wielościanu. Discrete Comput. Geom. 1992.]

Jeśli dany wielościan jest wypukły, znalezienie triangulacji jest łatwe, ale znalezienie triangulacji z minimalną liczbą czworościanów jest trudne dla NP. [Alexander Below, Jesús de Loera i Jürgen Richter-Gebert. Złożoność znalezienia małych triangulacji wypukłych 3-polytopów . J. Algorytmy 2004.]

Jeffε
źródło
2
Dzięki za wskazówki, Jeff. W szczególności uważam, że ostatni wspomniany wynik jest interesujący. Nieco zaskakujące jest to, że w płaszczyźnie liczba uproszczeń składających się na wielokąt jest stała, ale nie ma już większych wymiarów i jest trudna do optymalizacji. To jest dokładnie taka odpowiedź, na którą liczyłem.
Bob Fraser
16

Problemem wykonalności dla wielowymiarowych wymiarowych jest kandydat. Gdy d 3 , to jest on rozwiązany w czasie wielomianowym (według twierdzenia Steinitza ), ale gdy d 4 , jest to NP-trudne. Więcej informacji znajduje się w „ Przestrzeniach realizacji 4-polytopów są uniwersalne ” Richtera-Geberta i Zieglera (istnieje również wersja ARXIV ) oraz w książce „ Wykłady o polytopach ” (drugi druk) autorstwa Zieglera.dd3d4

Yoshio Okamoto
źródło
2
R
Dzięki, nie widziałem tego problemu wcześniej.
Bob Fraser
Ponownie, podobnie jak odpowiedź Davida Eppsteina, trudniejsze (prawdopodobnie) niż NP-zupełne.
Peter Shor,
11

Decyzja, czy przestrzeń metryczna jest izometrycznie osadzalna w R ^ 2, jest łatwa. Jednak trudno jest zdecydować się na osadzalność R ^ 3.

23

Papier

Zouzias
źródło
To także dobry przykład.
Suresh Venkat
-2

R2R3Z2Z3

k=2Z2Zkk>2.

Kaushik Shankar
źródło
co to znaczy powiedzieć, że 2SAT jest „w” R ^ 2?
Suresh Venkat
R2
11
-1: Nie widzę, jak 2SAT jest w R ^ 2. Nie rozumiem, w jaki sposób 2SAT jest „problemem geometrycznym”.
Robin Kothari,
Przepraszam, że nie przedstawiłem problemu geometrycznego, ale chociaż tytuł pyta o problemy geometryczne, dwa pytania w komentarzach nie określają, że jest to geometryczny. Ponadto, 2-spełnialność ma reprezentację graficzną znaną jako dopasowanie 2-wymiarowe, to znaczy w P, gdzie jako 3-spełnienie odpowiada dopasowaniu 3-wymiarowemu, czyli NP.
Kaushik Shankar
@Robin poszedłem naprzód i wyjaśniłem w moim oryginalnym komentarzu.
Kaushik Shankar