Enveloppe convexe
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

En mathématiques, l'enveloppe convexe d'un objet ou d'un ensemble d'objets est l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un...) convexe (En géométrie, un objet est convexe si pour toute paire de points { A , B } de cet objet, le segment [AB] qui les joint est entièrement contenu dans l'objet. Par exemple, un...) de taille minimale qui contient ces objets. L'enveloppe convexe (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...) 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 (Une surface désigne généralement la couche superficielle d'un objet. Le terme a plusieurs acceptions, parfois objet géométrique, parfois frontière physique, et est souvent...) de l'enveloppe convexe. Avec des ensembles dans des dimensions supérieures, l'enveloppe convexe d'un ensemble de points est un polyèdre (Traditionnellement, un polyèdre est une forme géométrique à 3 dimensions ayant des faces planes qui se rencontrent le long d'arêtes droites. Le mot polyèdre provient du grec classique...) 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é (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri Atlan), en...) varie :

  • Marche (La marche (le pléonasme marche à pied est également souvent utilisé) est un mode de locomotion naturel. Il consiste en un déplacement en appui alternatif sur les jambes, en position debout et en ayant toujours au...) de Jarvis
  • Parcours de Graham
  • Heuristique (L'heuristique (du grec heuriskêin, « trouver ») est l'utilisation de règles empiriques :) de Akl-Toussaint

Dimensions d'ordres supérieures

Pour un ensemble fini (En mathématiques, un ensemble E est dit fini si et seulement si E est vide ou s'il existe un entier n et une bijection de E dans l'ensemble des n premiers entiers naturels.) 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 (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) d'algorithmes sont quand même connus pour la dimension (Dans le sens commun, la notion de dimension renvoie à la taille ; les dimensions d'une pièce sont sa longueur, sa largeur et sa profondeur/son épaisseur, ou...) 3, mais aussi dans le cas général.

Page générée en 0.093 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique