Considérons le cas général où l’entrée de l’algorithme est un ensemble fini non ordonné de points sur un plan cartésien. Un cas particulier important, dans lequel les points sont donnés dans l’ordre de traversée de la limite d’un polygone simple, est décrit plus loin dans une sous-section séparée.
Si tous les points ne sont pas sur la même ligne, alors leur coque convexe est un polygone convexe dont les sommets sont certains des points de l’ensemble d’entrée. Sa représentation la plus courante est la liste de ses sommets ordonnés le long de sa frontière dans le sens horaire ou antihoraire. Dans certaines applications, il est pratique de représenter un polygone convexe comme une intersection d’un ensemble de demi-plans.
La borne inférieure de la complexité de calculEdit
Pour un ensemble fini de points dans le plan, la borne inférieure de la complexité de calcul pour trouver la coque convexe représentée comme un polygone convexe est facilement montrée comme étant la même que pour le tri en utilisant la réduction suivante. Pour l’ensemble x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}}
nombres à trier considérer l’ensemble des points ( x 1 , x 1 2 ) , … , ( x n , x n 2 ) {\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})}
de points dans le plan. Comme ils se trouvent sur une parabole, qui est une courbe convexe, il est facile de voir que les sommets de la coque convexe, lorsqu’ils sont traversés le long de la frontière, produisent l’ordre trié des nombres x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}}.
. Il est clair qu’un temps linéaire est nécessaire pour la transformation décrite des nombres en points puis l’extraction de leur ordre trié. Par conséquent, dans le cas général, la coque convexe de n points ne peut pas être calculée plus rapidement que le tri.
La borne inférieure standard Ω(n log n) pour le tri est prouvée dans le modèle d’arbre de décision de l’informatique, dans lequel seules les comparaisons numériques mais pas les opérations arithmétiques peuvent être effectuées ; cependant, dans ce modèle, les coques convexes ne peuvent pas du tout être calculées. Le tri nécessite également un temps Ω(n log n) dans le modèle algébrique d’arbre de décision du calcul, un modèle qui est plus adapté aux coques convexes, et dans ce modèle, les coques convexes nécessitent également un temps Ω(n log n). Cependant, dans les modèles d’arithmétique informatique qui permettent de trier les nombres plus rapidement que le temps O(n log n), par exemple en utilisant des algorithmes de tri d’entiers, les coques convexes planaires peuvent également être calculées plus rapidement : l’algorithme de scan de Graham pour les coques convexes consiste en une seule étape de tri suivie d’une quantité linéaire de travail supplémentaire.
Algorithmes optimaux sensibles à la sortieEdit
Comme indiqué ci-dessus, la complexité de la recherche d’une coque convexe en fonction de la taille d’entrée n est bornée inférieurement par Ω(n log n). Cependant, la complexité de certains algorithmes de coque convexe peut être caractérisée à la fois en termes de taille d’entrée n et de taille de sortie h (le nombre de points dans la coque). Ces algorithmes sont appelés algorithmes sensibles à la sortie. Ils peuvent être asymptotiquement plus efficaces que les algorithmes Θ(n log n) dans les cas où h = o(n).
La borne inférieure du temps d’exécution dans le pire des cas des algorithmes de coques convexes sensibles à la sortie a été établie à Ω(n log h) dans le cas planaire. Il existe plusieurs algorithmes qui atteignent cette complexité temporelle optimale. Le plus ancien a été introduit par Kirkpatrick et Seidel en 1986 (qui l’ont appelé « l’algorithme ultime de coque convexe »). Un algorithme beaucoup plus simple a été développé par Chan en 1996, et est appelé l’algorithme de Chan.
AlgorithmesEdit
Les algorithmes de coque convexe connus sont listés ci-dessous, classés par date de première publication. La complexité temporelle de chaque algorithme est énoncée en fonction du nombre de points d’entrée n et du nombre de points sur la coque. Notez que dans le pire des cas, h peut être aussi grand que n.
- Emballage de cadeaux, alias marche de Jarvis – O(nh)
L’un des algorithmes planaires les plus simples (bien qu’il ne soit pas le plus efficace en temps dans le pire des cas). Créé indépendamment par Chand & Kapur en 1970 et R. A. Jarvis en 1973. Il a une complexité temporelle O(nh), où n est le nombre de points dans l’ensemble, et h est le nombre de points dans la coque. Dans le pire des cas, la complexité est Θ(n2). - Scanner de Graham – O(n log n)
Algorithme légèrement plus sophistiqué, mais beaucoup plus efficace, publié par Ronald Graham en 1972. Si les points sont déjà triés par une des coordonnées ou par l’angle par rapport à un vecteur fixe, alors l’algorithme prend O(n) temps. - Quicksort
Créé indépendamment en 1977 par W. Eddy et en 1978 par A. Bykat. Tout comme l’algorithme quicksort, il a une complexité temporelle attendue de O(n log n), mais peut dégénérer en O(n2) dans le pire des cas. - Diviser et conquérir – O(n log n)
Un autre algorithme O(n log n), publié en 1977 par Preparata et Hong. Cet algorithme est également applicable au cas tridimensionnel. - Chaîne monotone, alias algorithme d’Andrew- O(n log n)
Publié en 1979 par A. M. Andrew. L’algorithme peut être considéré comme une variante du scan de Graham qui trie les points lexicographiquement par leurs coordonnées. Lorsque l’entrée est déjà triée, l’algorithme prend O(n) temps. - Algorithme de coque convexe incrémental – O(n log n)
Publié en 1984 par Michael Kallay. - Algorithme de Kirkpatrick-Seidel – O(n log h)
Le premier algorithme optimal sensible à la sortie. Il modifie l’algorithme diviser pour régner en utilisant la technique du mariage avant la conquête et la programmation linéaire à faible dimension. Publié par Kirkpatrick et Seidel en 1986. - Algorithme de Chan – O(n log h)
Un algorithme optimal sensible à la sortie plus simple créé par Chan en 1996. Il combine l’emballage cadeau avec l’exécution d’un algorithme O(n log n) (tel que le scan de Graham) sur de petits sous-ensembles de l’entrée.
H heuristique d’Akl-ToussaintEdit
L’heuristique simple suivante est souvent utilisée comme première étape dans les implémentations des algorithmes de coque convexe pour améliorer leurs performances. Elle est basée sur l’algorithme efficace de la coque convexe de Selim Akl et G. T. Toussaint, 1978. L’idée est d’exclure rapidement de nombreux points qui ne feraient de toute façon pas partie de la coque convexe. Cette méthode est basée sur l’idée suivante. Trouvez les deux points ayant les coordonnées x les plus basses et les plus hautes, et les deux points ayant les coordonnées y les plus basses et les plus hautes. (Chacune de ces opérations prend O(n).) Ces quatre points forment un quadrilatère convexe, et tous les points qui se trouvent dans ce quadrilatère (à l’exception des quatre sommets choisis initialement) ne font pas partie de la coque convexe. Trouver tous ces points qui se trouvent dans ce quadrilatère est également O(n), et donc, l’opération entière est O(n). En option, les points ayant la plus petite et la plus grande somme de coordonnées x et y ainsi que ceux ayant la plus petite et la plus grande différence de coordonnées x et y peuvent également être ajoutés au quadrilatère, formant ainsi un octogone convexe irrégulier, dont l’intérieur peut être éliminé en toute sécurité. Si les points sont des variables aléatoires, alors pour une classe étroite mais couramment rencontrée de fonctions de densité de probabilité, cette étape de prétraitement jetable fera qu’un algorithme de coque convexe s’exécutera en temps attendu linéaire, même si la complexité du pire cas de l’algorithme de coque convexe est quadratique en n.
Problèmes de coque convexe en ligne et dynamiquesModification
La discussion ci-dessus considère le cas où tous les points d’entrée sont connus à l’avance. On peut considérer deux autres paramètres.
- Problème de coque convexe en ligne : les points d’entrée sont obtenus séquentiellement un par un. Après l’arrivée de chaque point en entrée, la coque convexe pour l’ensemble des points obtenus jusqu’à présent doit être calculée efficacement.
- Entretien dynamique de la coque convexe : Les points d’entrée peuvent être séquentiellement insérés ou supprimés, et la coque convexe doit être mise à jour après chaque opération d’insertion/suppression.
L’insertion d’un point peut augmenter le nombre de sommets d’une coque convexe au plus de 1, tandis que la suppression peut convertir une coque convexe à n sommets en une coque convexe à n-1 sommets.
La version en ligne peut être traitée avec O(log n) par point, ce qui est asymptotiquement optimal. La version dynamique peut être traitée avec O(log2 n) par opération.
Polygone simpleEdit
La coque convexe d’un polygone simple est divisée par le polygone en morceaux, dont l’un est le polygone lui-même et les autres sont des poches délimitées par un morceau de la limite du polygone et une seule arête de la coque. Bien que de nombreux algorithmes aient été publiés pour le problème de la construction de la coque convexe d’un polygone simple, près de la moitié d’entre eux sont incorrects.McCallum et Avis ont fourni le premier algorithme correct.Une simplification ultérieure par Graham & Yao (1983) et Lee (1983) utilise seulement une structure de données à pile unique. Leur algorithme parcourt le polygone dans le sens des aiguilles d’une montre, en partant de son sommet le plus à gauche. Au fur et à mesure, il stocke une séquence convexe de sommets sur la pile, ceux qui n’ont pas encore été identifiés comme étant dans des poches. À chaque étape, l’algorithme suit un chemin le long du polygone, du sommet de la pile au sommet suivant qui ne se trouve pas dans l’une des deux poches adjacentes au sommet de la pile. Ensuite, tant que les deux sommets supérieurs de la pile ainsi que ce nouveau sommet ne sont pas en position convexe, il fait sauter la pile, avant de pousser finalement le nouveau sommet sur la pile. Lorsque la traversée dans le sens des aiguilles d’une montre atteint le point de départ, l’algorithme renvoie la séquence des sommets de la pile comme étant la coque.