Kompleksitas menghitung jalur terpendek di pesawat dengan hambatan poligonal

Misalkan kita diberi beberapa poligon sederhana terpisah di dalam pesawat, dan dua titik dan luar setiap poligon. Masalah jalur terpendek Euclidean adalah menghitung jalur terpendek Euclidean dari ke yang tidak memotong interior poligon apa pun. Untuk konkret, mari kita asumsikan bahwa koordinat dan , dan koordinat setiap titik poligon, adalah bilangan bulat.t s t s $s$$t$$s$$t$$s$$t$

Bisakah masalah ini diselesaikan dalam waktu polinomial?

Sebagian besar geometer komputasi akan langsung mengatakan ya, tentu saja: John Hershberger dan Subhash Suri menggambarkan sebuah algoritma yang menghitung jalur terpendek Euclidean dalam waktu , dan waktu ini terikat optimal dalam model pohon komputasi aljabar. Sayangnya, algoritma Hershberger dan Suri (dan hampir semua algoritma terkait sebelum dan sejak) tampaknya membutuhkan aritmatika nyata yang tepat dalam arti yang kuat berikut.$O(n\log n)$

Sebut jalur poligon valid jika semua simpul interiornya adalah simpul penghalang; setiap jalur terpendek Euclidean valid. Panjang setiap jalur yang valid adalah jumlah akar kuadrat dari bilangan bulat. Jadi, membandingkan panjang dua jalur yang valid membutuhkan membandingkan dua jumlah akar kuadrat, yang kita tidak tahu bagaimana melakukannya dalam waktu polinomial .

Selain itu, tampaknya sepenuhnya masuk akal bahwa contoh arbitrer dari masalah jumlah akar dapat dikurangi menjadi masalah jalur terpendek Euclidean yang setara.

Jadi: Apakah ada algoritma waktu polinomial untuk menghitung jalur terpendek Euclidean? Atau masalah NP-keras? Atau jumlah akar kuadrat-keras ? Atau sesuatu yang lain?

Beberapa catatan:

• Jalur terpendek di dalam (atau di luar) satu poligon dapat dihitung dalam waktu tanpa masalah numerik aneh menggunakan algoritma corong standar, setidaknya jika triangulasi poligon diberikan.$O(n)$

• Dalam praktiknya, aritmatika floating-point cukup untuk menghitung jalur yang terpendek hingga presisi floating-point. Saya hanya tertarik pada kompleksitas masalah yang sebenarnya .

• John Canny dan John Reif membuktikan bahwa masalah terkait dalam 3-ruang adalah NP-hard (secara moral karena mungkin ada jumlah eksponensial dari jalur terpendek). Joonsoo Choi, Jürgen Sellen, dan Chee-Keng Yap menggambarkan skema perkiraan waktu polinomial.

• Simon Kahan dan Jack Snoeyink mempertimbangkan masalah serupa untuk masalah terkait jalur jalur minimum dalam poligon sederhana.

Mungkin saya melewatkan sesuatu, tetapi jika kita mempertimbangkan kasus "mudah", di mana semua rintangan adalah titik, maka kita memiliki masalah menghitung jalur terpendek antara dua simpul dalam grafik planar, yang, jika saya tidak salah, diketahui sebagai jumlah dari akar kuadrat-keras.

PS. Saya ingin menambahkan komentar dan bukan jawaban, tetapi saya tidak dapat menemukan caranya. Saya minta maaf untuk itu. Bisakah admin tolong bantu saya dengan ini.