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

22

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

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(nlogn)

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.

Jeffε
la source
4
ce serait bien s'il y avait une liste de problèmes difficiles de somme des racines carrées.
Suresh Venkat
4
Cela ressemble à une question parfaite pour la théorie. Pourquoi tu ne le demandes pas?
Peter Shor

Réponses:

4

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?

Elias
la source
Vous avez besoin de 50 points de réputation pour publier un commentaire dans stackexchange. Plus de détails ici: cstheory.stackexchange.com/privileges/comment . Puisque vous fournissez des informations, je suppose que c'est correct de le poster comme réponse.
chazisop
1
Dans le cas «facile» où les obstacles sont des points, le chemin le plus court euclidien (ou plus formellement, le chemin infimal) est toujours un segment de ligne droite, et le calculer est trivial. Mais même pour les chemins les plus courts dans les graphes planaires avec des longueurs de bord euclidiennes, avez-vous une référence pour la dureté de la somme des racines? (Il n'est pas difficile de voir une réduction pour les graphiques à quatre dimensions, car chaque entier est la somme d'au plus quatre carrés parfaits.)
Jeffε
3
4k+1
Vous avez raison. Le cas «facile» est plutôt banal.
Elias