Algorithme de Chan

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

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 $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^[2]^,^[3].

Algorithme[modifier | modifier le code]

Version où le nombre de points h dans l'enveloppe convexe est connu[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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^[4], 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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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^[5], 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$ .

Références[modifier | modifier le code]

↑ (en) Timothy M. Chan, « Optimal output-sensitive convex hull algorithms in two and three dimensions », Discrete and Computational Geometry, vol. 16,‎ 1996, p. 361–368 (présentation en ligne)
↑ (en) Frank Nielsen, « Grouping and Querying : A Paradigm to Get Output-Sensitive Algorithms », Discrete and Computational Geometry, vol. 1763,‎ 2000, p. 250–257 (présentation en ligne).
↑ Frank Nielsen, « Algorithmes géométriques adaptatifs », sur INRIA, 1996, thèse de doctorat.
↑ B. Chazelle et Jiří Matoušek, « Derandomizing an output-sensitive convex hull algorithm in three dimensions », Computational Geometry, vol. 5,‎ 1995, p. 27–32 (présentation en ligne).
↑ (en) J. Hershberger, « Finding the upper envelope of n line segments in O(n log n) time », Information Processing Letters, vol. 33,‎ 1989, p. 169–174 (présentation en ligne).

[1] (en) Timothy M. Chan, « Optimal output-sensitive convex hull algorithms in two and three dimensions », Discrete and Computational Geometry, vol. 16,‎ 1996, p. 361–368 (présentation en ligne)

[2] (en) Frank Nielsen, « Grouping and Querying : A Paradigm to Get Output-Sensitive Algorithms », Discrete and Computational Geometry, vol. 1763,‎ 2000, p. 250–257 (présentation en ligne).

[3] Frank Nielsen, « Algorithmes géométriques adaptatifs », sur INRIA, 1996, thèse de doctorat.

[4] B. Chazelle et Jiří Matoušek, « Derandomizing an output-sensitive convex hull algorithm in three dimensions », Computational Geometry, vol. 5,‎ 1995, p. 27–32 (présentation en ligne).

[5] (en) J. Hershberger, « Finding the upper envelope of n line segments in O(n log n) time », Information Processing Letters, vol. 33,‎ 1989, p. 169–174 (présentation en ligne).

[1]

[2]

[3]

[4]

[5]