Diviser pour régner

Algorithme Quickhull
Consiste à chercher l'enveloppe convexe d'un nuage de points
Quart de tour d'une image
Méthode rapide pour effectuer le quart de tour d'une image
Algorithme de Karatsuba
Méthode rapide pour multiplier deux entiers. Peut être adapté pour multiplier deux polynômes.
FFT
Transformée de Fourier rapide. Impossible de surestimer l'importance de cet algorithme, mais un peu délicat à expliquer en deux lignes…
Deux points les plus proches
Recherche les deux points les plus proches dans un nuage de points.

L'alogorithme de Shamos est Huey est un exemple d'algorithme diviser pour régner. Il sert à déterminer des diagrammes de Voronoi. Mais c'est un algorithme théorique, pensable sur papier mais difficile à réaliser en pratique. D'ailleurs, pour déterminer des diagrammes de Voronoi, on préfère l'algorithme de Fortune comme décrit dans ce TD.