Algorithme de Chan
En géométrie algorithmique, l'algorithme de Chan[1] nommé d'après son inventeur Timothy M. Chan (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'algorithme de Kirkpatrick-Seidel et s'étend facilement à la dimension 3. Le paradigme utilisé dans l'algorithme s'appuie sur les travaux de Frank Nielsen[2],[3].
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/80/Convexhull.svg/220px-Convexhull.svg.png)
Algorithme
Version où le nombre de points h dans l'enveloppe convexe est connu
Dans un premier temps, nous présentons un algorithme qui utilise la valeur de et nous appelons ce paramètre
. Cette hypothèse n'est pas réaliste et nous allons la supprimer plus tard. L'algorithme est divisé en deux phases.
Phase 1 : pré-calcul d'enveloppes convexes pour des sous-ensembles
L'algorithme commence par partitionner en au plus
sous-ensembles
avec au plus
points dans chaque sous-ensemble. Puis, on calcule l'enveloppe convexe de chacun des sous-ensembles
en utilisant un algorithme en
(par exemple le parcours de Graham). Remarquons que, comme il y a
sous-ensembles de
points chacun, cette phase prend
opérations.
Phase 2 : calcul de l'enveloppe convexe
La seconde phase consiste à exécuter une marche de Jarvis en utilisant les enveloppes convexes précalculées dans la phase 1 pour accélérer le calcul. À chaque étape de la marche de Jarvis, on considère un point de l'enveloppe convexe et on cherche à calculer le point
tel que tous les autres points de
sont à droite de la ligne
. Si l'on connait l'enveloppe convexe
de
points, alors on peut calculer
en
en utilisant la recherche dichotomique. On calcule
pour tous les
sous-ensembles
de la phase 1 en
. Puis, on détermine
en utilisant la même technique que celle de la marche de Jarvis, mais en ne considérant que les points
où
est un sous-ensemble de la phase 1. Comme la marche de Jarvis répète le calcul d'un
fois, la seconde phase prend
opérations. Si
, elle prend
opérations.
Algorithme où h n'est pas connu
L'algorithme décrit précédemment utilise . Si
, nous nous en rendons compte dans la marche de Jarvis au bout de
étapes. Ainsi, si
, on prend
pour s'en rendre compte (et on ne calcule pas l'enveloppe convexe jusqu'au bout). Si
, on s'en rend compte aussi puisque l'algorithme s'arrête et calcule l'enveloppe convexe.
L'idée consiste alors à commencer l'algorithme avec une valeur petite pour (dans l'analyse qui suit on utilise 2, mais des nombres aux alentours de 5 marchent mieux en pratique), puis on augmente la valeur de
jusqu'à ce que
, et dans ce cas, on obtient l'enveloppe convexe.
Si on augmente la valeur de trop lentement, on a besoin de répéter les phases 1 et 2 trop de fois et le temps de d'exécution est trop grand. A contrario, si on augmente les valeurs de
trop vite, on risque d'atteindre une valeur de
beaucoup trop grande par rapport à
, et le temps d'exécution est trop grand. À la manière de la stratégie utilisée dans l'algorithme de Chazelle and Matoušek's[4], l'algorithme de Chan élève au carré la valeur de
à chaque itération sans dépasser
. En d'autres termes,
prend les valeurs 2, 4, 16, 256, etc. et à l'itération numéro
(en commençant à 0), on a
. Le temps d'exécution total de l'algorithme est
En dimension 3
Pour généraliser l'algorithme en dimension 3, on doit utiliser un autre algorithme en à la place du parcours de Graham et on doit utiliser une version 3D de la marche de Jarvis. La complexité temporelle reste en
.
Améliorations
Dans l'article de Chan, il y a des suggestions qui pourraient améliorer la performance de l'algorithme en pratique :
- Quand on calcule les enveloppes convexes des sous-ensembles, on peut éliminer les points qui ne sont dans l'enveloppe convexe pour les autres itérations.
- Quand
augmente, on peut calculer les nouvelles enveloppes convexes en fusionnant les enveloppes convexes précédentes au lieu de les recalculer à partir de zéro.
Extensions
L'article de Chan contient d'autres problèmes que l'on peut rendre sensible à la sortie en utilisant la même technique, par exemple :
- Calculer la courbe minimum (lower enveloppe) d'un ensemble de
segments. Hershberger[5], donne un algorithme en
qui peut être amélioré en
, où
est le nombre de segments dans la courbe minimum.
- Calculer une enveloppe convexe en dimension supérieure. On peut maintenir la complexité en
si
reste polynomial en
.