algorithme de Chan

En géométrie algorithmique, l'algorithme de Chan nommé d'après son inventeur (en), est un algorithme sensible à la sortie qui calcule l'enveloppe convexe d'un ensemble de points, en dimension 2 ou 3. La complexité temporelle est où est le nombre de points dans l'enveloppe convexe. En dimension 2, l'algorithme combine un algorithme en (par exemple le parcours de Graham) et la marche de Jarvis afin d'obtenir un algorithme en . L'algorithme de Chan est important car il est plus simple que l' et s'étend facilement à la dimension 3. Le paradigme utilisé dans l'algorithme s'appuie sur les travaux de Frank Nielsen.