Complexité du calcul des plus courts trajets dans le plan avec des obstacles polygonaux

Supposons que l'on nous donne plusieurs polygones simples disjoints dans le plan, et deux points et t à l' extérieur de chaque polygone. Le problème du chemin le plus court euclidien consiste à calculer le chemin le plus court euclidien de s à t qui ne coupe pas l'intérieur d'un polygone. Pour être concret, supposons que les coordonnées de s et t , et les coordonnées de chaque sommet de polygone, sont des entiers.$s$$t$$s$$t$$s$$t$

Ce problème peut-il être résolu en temps polynomial?

La plupart des géomètres informatiques diraient immédiatement oui, bien sûr: John Hershberger et Subhash Suri ont décrit un algorithme qui calcule les plus courts chemins euclidiens en temps , et cette limite de temps est optimale dans le modèle d'arbre de calcul algébrique. Malheureusement, l'algorithme de Hershberger et Suri (et presque tous les algorithmes associés avant et depuis) ​​semble nécessiter une arithmétique réelle exacte au sens fort suivant.$O(n\log n)$

Appelez un chemin polygonal valide si tous ses sommets intérieurs sont des sommets d'obstacles; chaque chemin le plus court euclidien est valide. La longueur d'un chemin valide est la somme des racines carrées d'entiers. Ainsi, comparer les longueurs de deux chemins valides nécessite de comparer deux sommes de racines carrées, ce que nous ne savons pas faire en temps polynomial .

De plus, il semble tout à fait plausible qu'une instance arbitraire du problème de la somme des racines carrées puisse être réduite à un problème euclidien équivalent sur le plus court chemin.

Donc: existe-t-il un algorithme polynomial pour calculer les plus courts chemins euclidiens? Ou le problème est-il NP-difficile? Ou la somme des racines carrées-difficile ? Ou autre chose?

Quelques notes:

• Les chemins les plus courts à l'intérieur (ou à l'extérieur) d'un polygone peuvent être calculés en temps sans aucun problème numérique étrange en utilisant l'algorithme d'entonnoir standard, au moins si une triangulation du polygone est donnée.$O(n)$

• En pratique, l'arithmétique en virgule flottante est suffisante pour calculer les chemins les plus courts jusqu'à une précision en virgule flottante. Je ne m'intéresse qu'à la complexité du problème exact .

• John Canny et John Reif ont prouvé que le problème correspondant dans 3 espaces est NP-difficile (moralement parce qu'il peut y avoir un nombre exponentiel de chemins les plus courts). Joonsoo Choi, Jürgen Sellen et Chee-Keng Yap ont décrit un schéma d'approximation du temps polynomial.

• Simon Kahan et Jack Snoeyink ont examiné des problèmes similaires pour le problème connexe des chemins de liaison minimale dans un polygone simple.

Peut-être que je manque quelque chose, mais si nous considérons le cas "facile", où tous les obstacles sont des points, alors nous avons le problème de calculer le chemin le plus court entre deux sommets dans un graphe planaire, qui, si je ne me trompe pas, est connu comme des sommes de racines carrées-dures.

PS. Je voulais ajouter un commentaire et non une réponse, mais je ne trouve pas comment. Je m'excuse pour cela. Les administrateurs peuvent-ils m'aider s'il vous plaît?