Algorithme de Chan

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
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 de points, en dimension 2 ou 3. La complexité temporelle est 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].

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

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

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

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

Dans l'article de Chan, il y a des suggestions qui pourrait 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[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 segments. Hershberger[5], donne un algorithme en qui peut être améliorer 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 .

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

  1. (en) Timothy M. Chan, « Optimal output-sensitive convex hull algorithms in two and three dimensions », Discrete and Computational Geometry, vol. 16,‎ , 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,‎ , p. 250–257 (présentation en ligne).
  3. Frank Nielsen, « Algorithmes géométriques adaptatifs », sur INRIA, , 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,‎ , 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,‎ , p. 169–174 (présentation en ligne).