Quickhull
# Quickhull

En géométrie algorithmique, quickhull est un algorithme pour le calcul de l'enveloppe convexe. C'est un algorithme du type diviser pour régner.

## Principe

Remarquons d'abord que l'enveloppe convexe d'un ensemble E de points est définie par un sous-ensemble F de E. Le principe de l'algorithme est le suivant. En premier lieu, on trouve le point le plus à gauche P et le point le plus à droite Q (en cas d'égalité on choisit de manière arbitraire). Les points P et Q appartiennent à l'enveloppe convexe. On peut alors résoudre le problème en trouvant l'enveloppe convexe des points au-dessus de la droite (PQ) et celle des points en dessous de la droite, puis en concaténant les listes de points (en ne répétant pas P et Q). Les sous-problèmes ont alors une forme plus restreinte que l'instance d'origine : on dispose de deux points sur une droite, telle que tous les points sont du même côté de la droite, disons à gauche de (PQ), et tous les points qui appartiennent à la droite sont dans le segment [PQ]. On trouve alors le point H le plus éloigné de la droite. L'enveloppe convexe des points au-dessus de (PQ) s'obtient alors en concaténant l'enveloppe convexe des points à gauche de (PH) et celle des points à gauche de (HQ). On peut calculer récursivement ces ensembles (ils sont dans la même configuration que précédemment).

* Les différentes étapes de l'algorithme Quickhull

## Complexité

L'algorithme a le même type de complexité en temps que l'algorithme de tri quicksort, c'est-à-dire $O(n^{2})$ dans le pire cas, et $O(n\log n)$ en moyenne.

## Histoire

L'algorithme apparaît dans le livre Computational Geometry - An Introduction en 1985, où les auteurs attribuent les idées à plusieurs articles des années $1970^,^,.$

