Algorithme de Chan

En géométrie algorithmique, l'algorithme de Chan nommé d'après son inventeur Timothy M. Chan (en), est un algorithme sensible à la sortie qui calcule l'enveloppe convexe d'un ensemble $P$ de $n$ points, en dimension 2 ou 3. La complexité temporelle est ${\mathcal {O}}(n\log h)$ où $h$ est le nombre de points dans l'enveloppe convexe. En dimension 2, l'algorithme combine un algorithme en ${\mathcal {O}}(n\log n)$ (par exemple le parcours de Graham) et la marche de Jarvis afin d'obtenir un algorithme en ${\mathcal {O}}(n\log h)$. 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.

Exemple d'une enveloppe convexe d'un ensemble de n = 10 points. L'enveloppe contient k = 5 points.

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 $h$ et nous appelons ce paramètre $m=h$. 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 $P$ en au plus $1+n/m$ sous-ensembles $Q$ avec au plus $m$ points dans chaque sous-ensemble. Puis, on calcule l'enveloppe convexe de chacun des sous-ensembles $Q$ en utilisant un algorithme en ${\mathcal {O}}(n\log n)$ (par exemple le parcours de Graham). Remarquons que, comme il y a ${\mathcal {O}}(n/m)$ sous-ensembles de ${\mathcal {O}}(m)$ points chacun, cette phase prend ${\mathcal {O}}(n/m){\mathcal {O}}(m\log m)={\mathcal {O}}(n\log m)$ 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 $p_{i}$ de l'enveloppe convexe et on cherche à calculer le point $p_{i+1}=f(p_{i},P)$ tel que tous les autres points de $P$ sont à droite de la ligne $p_{i}p_{i+1}$. Si l'on connait l'enveloppe convexe $Q$ de $m$ points, alors on peut calculer $f(p_{i},Q)$ en ${\mathcal {O}}(\log m)$ en utilisant la recherche dichotomique. On calcule $f(p_{i},Q)$ pour tous les ${\mathcal {O}}(n/m)$ sous-ensembles $Q$ de la phase 1 en ${\mathcal {O}}(n/m\log m)$. Puis, on détermine $f(p_{i},P)$ en utilisant la même technique que celle de la marche de Jarvis, mais en ne considérant que les points $f(p_{i},Q)$ où $Q$ est un sous-ensemble de la phase 1. Comme la marche de Jarvis répète le calcul d'un $f(p_{i},P)$ ${\mathcal {O}}(h)$ fois, la seconde phase prend ${\mathcal {O}}(n\log m)$ opérations. Si $m=h$, elle prend ${\mathcal {O}}(n\log h)$ opérations.

Algorithme où h n'est pas connu

L'algorithme décrit précédemment utilise $m=h$. Si $m<h$, nous nous en rendons compte dans la marche de Jarvis au bout de $m+1$ étapes. Ainsi, si $m<h$, on prend ${\mathcal {O}}(n\log m)$ pour s'en rendre compte (et on ne calcule pas l'enveloppe convexe jusqu'au bout). Si $m>h$, 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 $m$ (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 $m$ jusqu'à ce que $m>h$, et dans ce cas, on obtient l'enveloppe convexe.

Si on augmente la valeur de $m$ 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 $m$ trop vite, on risque d'atteindre une valeur de $m$ beaucoup trop grande par rapport à $h$, 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, l'algorithme de Chan élève au carré la valeur de $m$ à chaque itération sans dépasser $n$. En d'autres termes, $m$ prend les valeurs 2, 4, 16, 256, etc. et à l'itération numéro $t$ (en commençant à 0), on a $m=\min(n,2^{2^{t}})$. Le temps d'exécution total de l'algorithme est

$\sum _{t=0}^{\lceil \log \log h\rceil }{\mathcal {O}}\left(n\log(2^{2^{t}})\right)={\mathcal {O}}(n)\sum _{t=0}^{\lceil \log \log h\rceil }O(2^{t})={\mathcal {O}}\left(n\cdot 2^{1+\lceil \log \log h\rceil }\right)={\mathcal {O}}(n\log h).$

En dimension 3

Pour généraliser l'algorithme en dimension 3, on doit utiliser un autre algorithme en ${\mathcal {O}}(n\log n)$ à la place du parcours de Graham et on doit utiliser une version 3D de la marche de Jarvis. La complexité temporelle reste en ${\mathcal {O}}(n\log h)$.

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 $m$ 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 $n$ segments. Hershberger, donne un algorithme en ${\mathcal {O}}(n\log {}n)$ qui peut être amélioré en ${\mathcal {O}}(n\log {}h)$, où $h$ est le nombre de segments dans la courbe minimum.

• Calculer une enveloppe convexe en dimension supérieure. On peut maintenir la complexité en ${\mathcal {O}}(n\log {}h)$ si $h$ reste polynomial en $n$.