Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme de Chan
Résumé
vignette|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 nommé d'après son inventeur , 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.
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.
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.
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.