Enveloppe convexe - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs est disponible ici.
Analogie avec un élastique entourant des points dans le plan, l'enveloppe convexe est en bleu.
Analogie avec un élastique entourant des points dans le plan, l'enveloppe convexe est en bleu.

En mathématiques, l'enveloppe convexe d'un objet ou d'un ensemble d'objets est l'ensemble convexe de taille minimale qui contient ces objets. L'enveloppe convexe d'un ensemble A peut aussi être définie comme l'intersection de tous les ensembles convexes qui contiennent A.

Dans un plan, l'enveloppe convexe peut être comparée à un élastique relâché qui englobe tous les points et qui serait contracté. On peut étendre cette idée à des points dans l'espace avec un ballon qui se dégonflerait jusqu'à être en contact avec tous les points qui sont à la surface de l'enveloppe convexe. Avec des ensembles dans des dimensions supérieures, l'enveloppe convexe d'un ensemble de points est un polyèdre convexe dont la construction n'est pas aisée et nécessite des algorithmes particuliers.

Algorithmes

En 2D

Plusieurs algorithmes ont été inventés pour résoudre ce problème, leur complexité varie :

Dimensions d'ordres supérieures

Pour un ensemble fini de points, l'enveloppe convexe est un polyèdre convexe. Cependant, sa représentation n'est pas aussi facile que dans le cas du plan. Pour les dimensions strictement supérieures à 2, même si les arêtes du polyèdre sont connus, la construction des facettes n'est pas une tâche triviale. Un certain nombre d'algorithmes sont quand même connus pour la dimension 3, mais aussi dans le cas général.

Page générée en 0.035 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
A propos - Informations légales | Partenaire: HD-Numérique
Version anglaise | Version allemande | Version espagnole | Version portugaise