Marche de Jarvis

Diagramme de l'algorithme

Soit ${\displaystyle p_{0}}$ le point initial, par exemple le point d'abscisse minima, où on accroche le papier.

Le premier point rencontré par le papier sera ${\displaystyle p_{1}}$, puis ${\displaystyle p_{2}}$... jusqu'à retrouver ${\displaystyle p_{0}}$.

Plus formellement, il s'agit pour chaque nouveau sommet ${\displaystyle p_{i}}$ de l'enveloppe convexe trouvé, de chercher le suivant en calculant le point d'angle polaire minimal par rapport à ${\displaystyle p_{i}}$.

En pratique, on divise le parcours en deux : à partir du point d'abscisse minimale, puis à partir du point d'abscisse maximale.

 fonction marcheJarvis(E)
     p := un point d'abscisse minimale dans E
     L := liste vide
     répéter
           insérer p dans L
           p := point p' de E tel que [pp') est le plus incliné vers la gauche (1)
     jusqu’à p = p0
    retourner L

La ligne (1) s'effectue de la manière suivante :

    pointAGauche = premier point de E
    pour tout pointCandidat de E
          Si pointAGauche = p ou pointCandidat est à gauche du segment entre p et pointAGauche alors
                 pointAGauche=pointCandidat
    p := pointAGauche

Le cas pointAGauche=p est une situation assez rare, qui peut intervenir lorsqu'on étudie le second point candidat de E, et qu'aucun meilleur pointAGauche n'a encore été trouvé dans la boucle. Le corps de la boucle répéter - jusqu'à est exécuté autant de fois qu'il y a de points dans l'enveloppe convexe. La ligne (1) est en ${\displaystyle O(n)}$. D'où une complexité en ${\displaystyle O(nh)}$, où ${\displaystyle h}$ représente le nombre de sommets de l'enveloppe convexe.

La boucle interne vérifie tous les point dans l'ensemble E, et la boucle externe se répète pour chaque point de l'enveloppe. Donc le nombre total de tour de boucle est en ${\displaystyle O(nh)}$. Le temps d'exécution dépend de la taille de la sortie, on dit alors qu'il s'agit d'un algorithme sensible à la sortie.

Cependant, comme le temps d'exécution dépend linéairement du nombre d'arêtes de l'enveloppe, la marche de Jarvis peut être plus rapide que des algorithmes en ${\displaystyle O(n\log n)}$ (comme Parcours de Graham) lorsque le nombre h d'arêtes de l'enveloppe est plus petit que ${\displaystyle \log(n)}$. L'algorithme de Chan, un autre algorithme d'enveloppe convexe, combine la dépendance logarithmique de l'algorithme de Graham avec la sensibilité à la sortie de la marche de Jarvis, lui permettant d'atteindre une complexité en temps en ${\displaystyle O(n\log h)}$.

(fr) , Cours de l'université de Montpellier 2