Komplexität der Berechnung kürzester Wege in der Ebene mit polygonalen Hindernissen

Angenommen, wir erhalten mehrere disjunkte einfache Polygone in der Ebene und zwei Punkte und außerhalb jedes Polygons. Das Problem des euklidischen kürzesten Pfades besteht darin, den euklidischen kürzesten Pfad von nach zu berechnen, der das Innere eines Polygons nicht schneidet. Nehmen wir der Vollständigkeit halber an, dass die Koordinaten von und und die Koordinaten jedes Polygonknotens ganze Zahlen sind.$s$s t s $t$$s$$t$$s$$t$

Kann dieses Problem in polynomialer Zeit gelöst werden?

Die meisten rechnergestützten Geometer würden natürlich sofort Ja sagen: John Hershberger und Subhash Suri haben einen Algorithmus beschrieben, der euklidische kürzeste Pfade in berechnet , und diese Zeitgrenze ist im algebraischen rechnergestützten Baummodell optimal. Leider scheint der Algorithmus von Hershberger und Suri (und fast alle vor und nach ihm verwandten Algorithmen) eine exakte reelle Arithmetik im folgenden Sinne zu erfordern .$O(n\log n)$

Nennen Sie einen polygonalen Pfad gültig, wenn alle inneren Eckpunkte Hinderniseckpunkte sind. Jeder euklidische kürzeste Weg ist gültig. Die Länge eines gültigen Pfades ist die Summe der Quadratwurzeln von ganzen Zahlen. Der Vergleich der Längen zweier gültiger Pfade erfordert daher den Vergleich zweier Summen von Quadratwurzeln, was wir in der Polynomzeit nicht wissen .

Darüber hinaus erscheint es durchaus plausibel, dass eine beliebige Instanz des Problems der Quadratwurzelsumme auf ein äquivalentes euklidisches Problem des kürzesten Pfades reduziert werden könnte.

Also: Gibt es einen Polynom-Zeit-Algorithmus, um die kürzesten euklidischen Pfade zu berechnen? Oder ist das Problem NP-schwer? Oder die Summe der Quadratwurzeln ? Oder etwas anderes?

Ein paar Anmerkungen:

• Kürzeste Pfade innerhalb (oder außerhalb) eines Polygons können in Zeit ohne merkwürdige numerische Probleme unter Verwendung des Standard-Trichteralgorithmus berechnet werden, zumindest wenn eine Triangulation des Polygons gegeben ist.$O(n)$

• In der Praxis reicht die Gleitkomma-Arithmetik aus, um Pfade zu berechnen, die bis zur Gleitkomma-Genauigkeit am kürzesten sind. Mich interessiert nur die Komplexität des genauen Problems.

• John Canny und John Reif haben bewiesen, dass das entsprechende Problem im 3-Raum NP-schwer ist (moralisch, weil es eine exponentielle Anzahl von kürzesten Wegen geben kann). Joonsoo Choi, Jürgen Sellen und Chee-Keng Yap beschrieben ein polynomialzeitliches Approximationsschema.

• Simon Kahan und Jack Snoeyink betrachteten ähnliche Probleme für das verwandte Problem der Pfade mit minimalen Verbindungen in einem einfachen Polygon.

Vielleicht vermisse ich etwas, aber wenn wir den "einfachen" Fall betrachten, in dem alle Hindernisse Punkte sind, dann haben wir das Problem, den kürzesten Weg zwischen zwei Eckpunkten in einem ebenen Graphen zu berechnen, der, wenn ich mich nicht irre, bekannt ist als Quadratwurzelsummen-hart.

PS. Ich wollte einen Kommentar hinzufügen und keine Antwort, aber ich kann nicht finden, wie. Ich entschuldige mich dafür. Können die Administratoren mir bitte dabei helfen?