Problemy geometryczne, które są NP kompletne w

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).$R^1$$R^d$$d\geq2$

Czy ktoś wie o problemie, który jest polytime rozwiązywalne dla i R 2 , ale NP-zupełny dla R d , d ≥ 3 ? $R^1$$R^2$$R^d,d\geq3$

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 ?$R^k$$R^{k-1}$$k\geq3$

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/

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

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

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.$d$$d \le 3$$d \ge 4$

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

$\ell_\infty^2$$\ell_\infty^3$

Papier

$R^2$$R^3$$Z^2$$Z^3$

$k = 2$$Z^2$$Z^k$$k > 2$.