Diagramme de Voronoï
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.
Un diagramme de Voronoï.
Un diagramme de Voronoï.

En mathématiques, un diagramme de Voronoï (aussi appelé décomposition de Voronoï ou partition de Voronoï du nom du mathématicien russe Georgi Fedoseevich Voronoï (1868 - 1908)) est une décomposition (En biologie, la décomposition est le processus par lequel des corps organisés, qu'ils soient d'origine animale ou végétale dès l'instant qu'ils sont privés de vie,...) particulière d’un espace métrique (En mathématiques, un espace métrique est un ensemble au sein duquel une notion de distance entre les éléments de l'ensemble est définie. C'est un cas particulier d'espace topologique.) déterminée par les distances à un 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...) discret d’objets de l’espace, en général un ensemble discret de points.

Définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les...)

On se place dans un espace euclidien (Un espace euclidien, dans la conception actuelle, est un espace vectoriel ou affine réel de dimension finie muni d'un produit scalaire. Dans un tel espace, on peut...) E. soit S 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 n points de E; les éléments de S sont appelés centres, sites ou encore germes.

On appelle région de Voronoï ou cellule de Voronoï associée à un élément p de S l’ensemble des points qui sont plus proches de p que de tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) autre point (Graphie) de S.

Vor_s(p)=\{ x \in E\  /\  \forall q \in S\  d(x,p) \le d(x,q) \}

Pour deux point a et b de S, l’ensemble Π(a,b) des points équidistant de a et b est un hyperplan (En algèbre linéaire, les hyperplans sont définis dans la théorie des espaces vectoriels.) affine (En mathématiques, affine peut correspondre à :) (un sous-espace affine de co-dimension 1). Cet hyperplan est la frontière (Une frontière est une ligne imaginaire séparant deux territoires, en particulier deux États souverains. Le rôle que joue une frontière peut fortement varier suivant les...) entre l’ensemble des points plus proche de a que de b, et l’ensemble des points plus proches de b que de a.

\Pi(p,q)=\{ x \in E\ /\ d(x,p) = d(x,q) \}

On note H(a,b) le demi espace délimité par cet hyperplan contenant a, il contient alors tout les points plus proches de a que de b. La région de Voronoï associée à a est alors l’intersection des H(a,b)b parcourt S\{a}.

H(p,q)=\{ x \in E\  /\  d(x,p) \le d(x,q) \}

Vor_s(p)=\bigcap_{q \in S \backslash \{ p\} } H(p,q)

Les régions de Voronoï sont des polytopes convexes en tant qu’intersection de demi espaces. L’ensemble de tels polygones partitionne E, et est la partition de Voronoï correspondant à l’ensemble S.

En 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 bien...) 2 il est facile de tracer ces partitions, on les appelle dans ce cas parfois diagrammes de Voronoi. On se base sur le fait que la frontière entre les cellules de Voronoi de deux germes distincts se situe forcément sur la médiatrice (En géométrie plane, la médiatrice d'un segment est l'ensemble des points équidistants des extrémités du segment. Cet ensemble est la droite passant par le milieu du segment et qui est perpendiculaire au...) qui sépare ces deux germes. En effet, les points de cette médiatrice sont équidistants des deux germes donc on ne peut pas affirmer qu'il se situent dans l'une ou l'autre cellule de Voronoi. Pour un ensemble de germes, le diagramme (Un diagramme est une représentation visuelle simplifiée et structurée des concepts, des idées, des constructions, des relations, des données statistiques, de l'anatomie etc. employé dans tous les...) de Voronoi se construit donc en déterminant les médiatrices de chaque couple de germes. Un point d'une médiatrice appartient alors à une frontière de Voronoi s'il est équidistant d'au moins deux germes et qu'il n'existe pas de distance plus faible entre ce point et un autre germe (En botanique, un germe est un embryon de plante contenu dans une graine. Le terme désigne également une excroissance qui se développe depuis un tubercule. Germe est un synonyme de plicitatus. La germination...) de l'ensemble.

Le diagramme de Voronoï est le dual de la triangulation de Delaunay (La triangulation de Delaunay d'un ensemble de n points est l'unique triangulation telle qu'un cercle passant par les trois points d'un triangle ne contienne aucun...), on peut définir la triangulation (En géométrie et trigonométrie, la triangulation est une technique permettant de déterminer la position d'un point en mesurant les angles entre ce point et d'autres points de...) de Delaunay à partir du diagramme de Voronoï, deux points p et q créent une arête dans le graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) de Delaunay si et seulement si les régions de Voronoï associées à p et q sont adjacentes.

DEL(S)=\{(p,q) \in S^2 \ / \ Vor_s(p) \cap Vor_s(q)\ne \empty \}

Histoire

L’usage informel des diagrammes de Voronoï remonte à Descartes en 1644. Dirichlet a utilisé des diagrammes de Voronoï en dimension 2 ou 3 dans son étude des formes quadratiques en 1850.

Le physicien (Un physicien est un scientifique qui étudie le champ de la physique, c'est-à-dire la science analysant les constituants fondamentaux de l'univers et les forces qui les relient. Le mot physicien dérive du grec, qui connaît la...) britannique John Snow a utilisé un diagramme de Voronoï en 1854 pour montrer que la majorité des personnes mortes dans l’épidémie de choléra (Le choléra est une toxi-infection entérique épidémique contagieuse due à la bactérie Vibrio cholerae, ou bacille virgule, découverte par Pacini en 1854 et redécouverte par Koch en 1883. Elle est...) de Soho (SoHO (Solar and Heliospheric Observatory, soit observatoire solaire et heliospherique) est une sonde spatiale placée en orbite autour du Soleil. Son objectif principal est d'étudier le Soleil. Il est le fruit d'une...) vivait plus près de la pompe (Une pompe est un dispositif permettant d'aspirer et de refouler un fluide.) infectée de Broad Street que de n’importe quelle autre pompe.

Les diagrammes de Voronoï portent le nom du mathématicien (Un mathématicien est au sens restreint un chercheur en mathématiques, par extension toute personne faisant des mathématiques la base de son activité principale. Ce terme recouvre une large palette de compétences et de...) russe Georgy Fedoseevich Voronoï (ou Voronoy) qui a défini et étudié le cas général en dimension n en 1908. Les diagrammes de Voronoi qui sont utilisés en géophysique et en météorologie (La météorologie a pour objet l'étude des phénomènes atmosphériques tels que les nuages, les précipitations ou le vent dans le but de comprendre comment ils se forment et évoluent en fonction des...) pour analyser des données (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.) de distributions spatiales (comme les mesures de chutes de pluie) sont appelés polygones de Thiessen du nom du météorologiste américain Alfred H. Thiessen.

Exemple

L'exemple suivant reprend les mêmes points que l'exemple de la triangulation de Delaunay : Image:Exemple_de_diagramme_de_Voronoï.png

Algorithmes

L'algorithme de Steven Fortune (1987, Laboratoires Bell (Bell Aircraft Corporation est un constructeur aéronautique américain fondé le 10 juillet 1935. Après avoir construit des avions de combat durant la Seconde...) AT&T), démontré comme optimal, permet de calculer le diagramme de Voronoï d'un ensemble de n points dans le temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) O(nlog(n)).

Applications

Les diagrammes de Voronoï sont utilisés, ou réinventés sous de nombreux noms, dans différents domaines. Ils interviennent souvent lorsque l'on cherche à partitionner l'espace en sphères d'influence :

  • Reconstruction de données géographiques optimales, pour un simulateur de vol (Un simulateur de vol est une application au domaine de l'aéronautique, du pilotage des aéronefs en particulier, des techniques de simulation de phénomènes physiques.) par exemple.
  • Effet de Mosaïque dans un logiciel (En informatique, un logiciel est un ensemble d'informations relatives à des traitements effectués automatiquement par un appareil informatique. Y sont...) de retouche d'image.
  • Construction d'un dôme () géodésique (En géométrie, une géodésique désigne le chemin le plus court, ou l'un des chemins s'il en existe plusieurs, entre deux points d'un espace une fois qu'on s'est donné un moyen de mesurer les distances,...) dual
  • Partition des structures spatiales des populations d'étoiles.
  • Diagnostic (Le diagnostic (du grec δι?γνωση, diágnosi, à partir de δια-, dia-, „par, à travers, séparation,...) de cellules cancéreuses.
  • Modélisation de microstructures telles que certains aciers.
  • Simulation de la circulation (La circulation routière (anglicisme: trafic routier) est le déplacement de véhicules automobiles sur une route.) des fluides dans les milieux poreux.
  • Calculs de trajectoire (La trajectoire est la ligne décrite par n'importe quel point d'un objet en mouvement, et notamment par son centre de gravité.) en robotique mobile.
  • ...
Page générée en 0.097 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