Algorithme de Shamos
# Algorithme de Shamos

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

## Principe

Le principe de l'algorithme est le suivant pour un ensemble de points E. On décompose notre ensemble E en deux ensembles E1 et E2. On calcule ensuite par récursivité l'enveloppe convexe de E1 et E2. Finalement, on construit l'enveloppe convexe de E à partir de celles de E1 et E2 où EC(E) = EC(EC(E1) U EC(E2)).

## L'algorithme

La quatrième étape repose sur l'utilisation d'un algorithme de fusion.

## Complexité

L'algorithme a une complexité en temps de O(n.log(n)).

## Histoire

L'algorithme apparaît dans le livre Computational Geometry - An Introduction en 1985, de Michael Ian Shamos et Franco P.Preparata.

