Masalah geometris yang NP-lengkap dalam

Sejumlah masalah geometris mudah ketika dipertimbangkan dalam , tetapi NP-lengkap dalam R d untuk d ≥ $R^1$$R^d$$d\geq2$ (termasuk salah satu masalah favorit saya, unit kap disk).

Adakah yang tahu masalah yang bisa dipecahkan dengan polytime untuk dan R 2 , tetapi NP-complete untuk R d , d ≥ $R^1$$R^2$$R^d,d\geq3$ ?

Lebih umum, melakukan masalah ada yang NP-lengkap untuk tapi polytime dipecahkan untuk R k - 1 , dimana k ≥ 3 ?$R^k$$R^{k-1}$$k\geq3$

Atur penutup dengan setengah spasi.

Diberikan satu set poin di pesawat, dan satu set pesawat setengah-setengah menghitung jumlah pesawat setengah-setengah yang mencakup set titik dapat diselesaikan dalam waktu polinomial di pesawat. Namun masalahnya adalah NP keras dalam 3d (lebih sulit daripada menemukan penutup min dengan subset disk poin dalam 2d). Dalam 3d Anda diberi subset ruang setengah dan poin, dan Anda mencari jumlah ruang setengah yang mencakup titik.

Algoritma polytime dalam 2d dijelaskan di sini: http://valis.cs.uiuc.edu/~sariel/papers/08/expand_cover/

Ini tidak seperti yang Anda tanyakan, karena versi 3d bahkan lebih sulit daripada NP-complete, tetapi: Menemukan jalur terpendek antara dua titik di antara hambatan poligon di dalam pesawat adalah dalam waktu polinomial (paling sederhana, buat grafik visibilitas kedua terminal) dan simpul poligon dan menerapkan Dijkstra, ada juga algoritma O (n log n) yang lebih rumit karena Hershberger dan Suri, SIAM J. Comput. 1999) tetapi menemukan jalur terpendek di antara hambatan polihedral di 3d adalah PSPACE-complete (Canny dan Reif, FOCS 1987).

Segala poligon non-cembung di dalam pesawat dapat di-triangulasi dalam waktu O (n) tanpa poin Steiner; yaitu, setiap simpul dari triangulasi adalah suatu puncak dari poligon. Selain itu, setiap triangulasi memiliki tepat segitiga n-2.

Namun, menentukan apakah polyhedron non-cembung di R ^ 3 dapat triangulasi tanpa poin Steiner adalah NP-lengkap. Hasil NP-hardness berlaku bahkan jika Anda diberi triangulasi dengan satu poin Steiner, jadi bahkan mendekati jumlah minimum poin Steiner yang diperlukan adalah NP-hard. [Jim Ruppert dan Raimund Seidel. Pada Kesulitan Triangulasi Tiga Dimensi Nonconvex Polyhedra. Komputasi Terpisah. Geom. 1992.]

Jika polyhedron yang diberikan adalah cembung, menemukan triangulasi itu mudah, tetapi menemukan triangulasi dengan jumlah minimum tetrahedra adalah NP-hard. [Alexander Below, Jesús de Loera, dan Jürgen Richter-Gebert. Kompleksitas menemukan triangulasi kecil cembung 3-polytopes . J. Algoritma 2004.]

Masalah realisasi untuk polytopes dimensional adalah kandidat. Ketika d ≤ 3 , itu polinomial-waktu dipecahkan (oleh teorema Steinitz ' ), tetapi ketika d ≥ 4 , ini NP-hard. Untuk informasi lebih lanjut, silakan lihat " Ruang realisasi 4-polytopes bersifat universal " oleh Richter-Gebert dan Ziegler (ada juga versi arxiv ), dan buku " Lectures on Polytopes " (cetakan kedua) oleh Ziegler.$d$$d \le 3$$d \ge 4$

Memutuskan apakah ruang metrik dapat disematkan secara isometrik ke dalam R ^ 2 adalah mudah. Namun, NP-sulit untuk memutuskan embeddability R ^ 3.

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

Kertas

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

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