title: Algorithme de Shamos
text: # 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.
  
  