Ê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
Calcul de l'enveloppe convexe
Résumé
En algorithmique géométrique, le calcul de l'enveloppe convexe est un problème algorithmique. Il consiste, étant donné un ensemble de points, à calculer leur enveloppe convexe.
L'enveloppe convexe d'un ensemble de points est le plus petit ensemble convexe qui les contient tous. C'est un polyèdre dont les sommets sont des points de l'ensemble. Le calcul de l'enveloppe convexe consiste à calculer une représentation compacte de l'enveloppe, le plus souvent les sommets de celle-ci.
C'est un problème ayant de nombreuses applications, par exemple en analyse de forme et reconnaissance de formes, et qui est central en géométrie algorithmique.
Le cas planaire est le cas où les points sont disposés dans le plan. On mesure la complexité en temps en fonction du nombre de points de l'entrée n, et du nombre de points sur l'enveloppe h. Il existe de nombreux algorithmes pour ce cas.
L'idée de la marche de Jarvis (ou gift wrapping algorithm) est d' « envelopper » l'ensemble de points dans un « papier cadeau » : on accroche ce papier à l'un des points, on le tend, puis on tourne autour du nuage de points. La complexité de l'algorithme est O(nh).
Le parcours de Graham (aussi appelé Graham scan) consiste à trouver le point de plus petite abscisse, à trier tous les autres points par rapport à l'angle qu'ils font avec ce dernier (et l'axe des abscisses), puis à considérer les triplets de points successifs, pour déterminer lesquels sont dans l'enveloppe. Sa complexité est celle du tri, c'est-à-dire O(n log(n)).
L'algorithme de Chan procède en plusieurs étapes. D'abord un partitionnement des points en plusieurs groupes, puis le calcul des enveloppes convexes de ces groupes avec un algorithme en O(n log(n)) (comme le parcours de Graham), et enfin une marche de Jarvis utilisant ces enveloppes déjà calculées. Sa complexité est en O(n log(h)).
Quickhull est un algorithme de type diviser pour régner. Sa complexité moyenne est O(n.log(n)). Sa complexité dans le pire des cas est O(n2).
L'algorithme de Shamos est un algorithme de type diviser pour régner.
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.
Cours associés (3)
MGT-418: Convex optimization
This course introduces the theory and application of modern convex optimization from an engineering perspective.
MATH-476: Optimal transport
The first part is devoted to Monge and Kantorovitch problems, discussing the existence and the properties of the optimal plan. The second part introduces the Wasserstein distance on measures and devel
EE-556: Mathematics of data: from theory to computation
This course provides an overview of key advances in continuous optimization and statistical analysis for machine learning. We review recent learning formulations and models as well as their guarantees
Séances de cours associées (23)
Convexité géodésique : théorie et applications
Explore la convexité géodésique dans les espaces métriques et ses applications, en discutant des propriétés et de la stabilité des inégalités.
Ensembles de convex : séance de cours MGT-418
Sur Convex Optimization couvre l'organisation des cours, les problèmes d'optimisation mathématique, les concepts de solution et les méthodes d'optimisation.
La dualité dans la programmation linéaire
Explore le concept de dualité dans la programmation linéaire, en discutant de la relation entre les problèmes primaires et duaux.
Publications associées (47)