NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 08/12/2014

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

Géométrie

 

Débutants

Géométrie

Distances

 

Glossaire

Géométrie

 

 

INDEX

 

Géométrie

Distance

Médiatrice

Diagramme de Voronoï

Lycée et +

 

Sommaire de cette page

>>> Approche

>>> Construction

>>> Définition et interprétation

>>> Voronoï et Delaunay

>>> Propriétés

>>> Historique et applications

>>> Anglais

 

Source Voro++

 

 

 

 

Diagramme de VORONOÏ

et partition de Delaunay

(réseau de Dirichlet ou polygone de Thiessen)

 

L'offre de cinémas est importante dans ma région. Mais quelle est la salle la plus proche? Comment gérer les situations de collision potentielles en navigation maritime? Et bien d'autres applications >>>

 

Ces outils, qui traitent des réseaux de points, sont fondamentaux en géométrie algorithmique, c'est-à-dire traitée par ordinateurs.

 

Trois domaines d'investigations:

*    Études de leurs propriétés géométriques et même statistiques;

*    Construction des diagrammmes par ordinateur; et

*    Application à la modélisation des phénomènes.

 

Le cas où le réseau de points dans l'espace est régulier est d'un grand intérêt pour l'étude de la cristallographie

 

Mais avant tout, c'est un bon sujet de découverte et d'amusement, abordable avec un bagage élémentaire en géométrie.

Anglais: Voronoi diagrams or Voronoi tessallations or Dirichlet's tessellation

 

 

Georgy Voronoï ou Voronoy (1868-1908)

Mathématicien né en Ukraine et mort en Pologne.

Travaux sur: racines des équations du troisième degré, nombres algébriques, nombres de Bernoulli,  algorithmes pour les fractions continues, la géométrie des nombres, les fonctions transcendantes.

 

Ses diagrammes sont utilisés dans l'analyse des données distribuées spatialement. Ils sont à la base de la démonstration de la conjecture de Kepler sur l'empilement des sphères.

 

Boris Delone ou Delaunay et Waclaw Sierpinski furent ses élèves.

Voir Contemporains

 

 

 

Approche

 

 

*      Deux cinémas, l'un en A et l'autre en B. Là où je suis en ce moment, j'ai plutôt intérêt à me diriger vers A (si on y joue le film que je souhaite voir).

*      La frontière de choix passe par la médiatrice MM' de AB. Chaque fois que je me trouve sur la médiatrice je suis à égale distance de chacun des points A et B.

 

 

*    Un troisième cinéma s'est implanté dans la région. Nous avons trois zones  délimitées par les trois médiatrices. Celles-ci, pour tout triangle, sont concourantes en un point.

Les lignes vertes forment le diagramme de Voronoï et le point de concours est un point de Voronoï.
Les points A, B et C sont appelés les germes et les sites.

 

Tous les points situés dans une zone (un polygone convexe) de Voronoï sont plus proches de son site que de tous les autres sites.

 

Exemple: si les sites sont des garages et si je suis en panne, j'ai intérêt à me diriger vers le garage de la zone où je me trouve, c'est le plus proche.

 

*    Avec quatre points la construction n'est pas plus compliquée. Les médiatrices s'arrêtent à l'intersection avec une autre.

 

 

Construction

 

 

*      On commence par un point central et les segments le liant aux autres sites proches (en rouge).

*      On trace les médiatrices de tous ces segments. Elles forment un polygone autour du point considéré.

*      On termine en traçant les médiatrices des segments formés par les couples proches. Chacune rejoint l'un des sommets du polygone (points de Voronoï).

 

 

 

 

 

*      Exemple de diagramme de Voronoï à dix points.


*      En comptant les frontières extérieures, chaque point (site) est à l'intérieur d'un polygone convexe. Tous les points de ce polygone sont plus proches du point interne que de tous les autres points.
Il s'agit d'un réseau en nid d'abeille irrégulier.

 

 

 

Définition et interprétation

Un diagramme de Voronoï s'applique à un ensemble de points E d'un plan, appelés sites ou germes. Le diagramme est un réseau comportant des polygones convexes. Chacun délimite la zone dans laquelle tout point est plus proche de son germe que de tous les autres germes. Voir formulation

Le terme "germe" vient d'une vision dynamique de formation de ces diagrammes. Imaginez un cercle croissant à une vitesse constante, attaché à chaque point. Quand deux cercles se rencontrent la frontière forme une frontière linéaire, médiatrice des deux germes responsables. La croissance arrivée à son terme forme une partition du plan dite décomposition de Voronoï. Chaque région est l'ensemble des points les plus proches d'un germe.

 

 

 

Diagramme de Voronoï et partition de Delaunay

*    Vous avez déjà remarquez que pour engendrer un diagramme de Voronoï certaines médiatrices sont utilisée et pas d'autres.

*    Dit-autrement, certaines connexions entre les points sont mises en jeu et pas d'autres. Les points trop lointains n'ont pas d'influence.

*    Les segments utiles forment une triangulation ou partition du plan dite de Delaunay.

*    En mécanique une structure en triangulation de Delaunay est le maillage le plus efficace. Elle minimise les carrés des aires des triangles.

 

 

 

Propriétés

 

Géométriques

*    Un point de Voronoï est de degré 3.

*      Un raisonnement impliquant la relation d'Euler montre que:

*      quantité d'arêtes max.        = 3n – 6;

*      quantité de sommets max. = 2n – 5; et

*      chaque arête appartient à exactement deux régions.

*      Chaque sommet et le centre d'un cercle vide passant par trois sites.
Chaque point sur une arête est le centre d'un cercle vide passant par deux sites.



Générales

*    Les deux représentations (Voronoï et Delaunay) sont des graphes planaires (qui ne se croisent pas dans le plan).

*    L'un est le dual de l'autre. Chacun représente la même réalité.

*    En géométrie, ce diagramme peut servir à trouver le plus grand cercle vide dans une région de Voronoï.

*    L'algorithme de Steven Fortune (1987) engendre le diagramme par croissance de paraboles. Il a été démontré comme asymptotiquement optimum. Voir exemple animé et code en Fortune's algorithmWikipedia

*      Le diagramme de Voronoï classique utilise la notion classique de distance (euclidienne) où le théorème de Pythagore s'applique. Cette notion peut être généralisée en adoptant d'autres définitions de la distance, comme, par exemple, le suivi de chemin à angle droit (comme les rues de Manhattan). Une autre de voie de généralisation consiste à s'intéresser à un groupe de points proche d'un point donné.
 

*      Les diagrammes de Voronoï sont de bons candidats pour l'étude de la géométrie algorithmique. Nombreux sites sur Internet avec le détail du code.
 

Voir Graphe et le problème des quatre couleurs

 

 

Historique et applications

 

Chronologie

1644 – René Descartes utilise de tels diagrammes pour représenter l'espace du système solaire.

1840 – Gauss observe le premier un rapport avec les formes quadratiques.

1850 – Dirichlet exploite l'observation de Gauss et démontre l'unicité de la réduction des formes quadratiques.

1907 – Voronoï les utilise en les généralisant à plus de deux dimensions.

1934 – Delaunay introduit sa partition pour des réseaux irréguliers; méthode de croissance du cercle vide.

1854 – Épidémie de choléra à Londres. Cet outil permit à John Snow de mettre en évidence un lieu infecté fautif, en fait une pompe dans le quartier de Soho.

v. 1980 – Application aux polytopes (hyperpolyèdres).

v. 2000 – Application modélisation des surfaces, à leur échantillonnage. Comme les splines le font aussi.

Depuis: utilisation en images calculées, épidémiologie, géophysique, météorologie, navigation, robotique …

 

Applications typiques

*    borne d'appel de secours,

*    cristallographie,

*    croissance de cellules végétales,

*    empilement des sphères

*    espace occupés par les arbres dans la forêt,

*    partition du cosmos selon étoiles et galaxies,

*    évolution de cellules cancéreuses,

*    prévisions climatiques, 

*    proximités entre atomes,

*    relais de communication,

*    restaurants le plus proche,

*    taches sur la peau (girafes),

*    zones de collision potentielle en navigation,

*      zones maritimes exclusives (ZEE)

*      etc.

Ces outils, qui traitent des réseaux de points, sont fondamentaux en géométrie algorithmique, c'est-à-dire traitée par ordinateurs: images calculées, conception assistée par ordinateur, reconnaissance de caractères, recherche opérationnelle …

 

 

 

 

English corner

 

*    The Voronoi diagram is one of the most fundamental data structures in computational geometry.

*      Given some number of points in the plane, their Voronoi diagram divides the plane according to the nearest-neighbor rule: each point is associated with the region of the plane closest to it.

*      Definition of the Voronoi diagram: Let S denote a set of n points, called (sites) in the plane. For two distinct sites p, q  S, the dominant of p over q is defined as the subset of the plane being at least as close to p as to q. Formally, with delta denoting the euclidean distance:



*      The planar Voronoi diagram and the Delaunay triangulation are duals in a graph theoretical sense. Voronoi vertices correspond to Delaunay triangles.

 

 

 

 

 

 

Suite

*    Empilement des sphères

*    Densité des disques

*    Hypersphère et Univers

Voir

*    Construction à la règle et au compas

*    Énigmes classiques

*    GéométrieIndex

*    Jeux diversIndex

*    Le cube

*    Les nombres cubes

*    Les trois filles

*    Pliages

*    Polyèdres

*    Polytopes

*    Quadrature du cercle

Sites

*    Reconstruire des surfaces pour l'imagerie – Interstices: explications et animations interactives

*    Spherical Voronoi diagram  de jason Davies -  Interactif. Voir son Voronoï des aéroports

*    Un petit peu de géométrie algorithmique – Frank HétroyEnsimag (pdf, supérieur))

*    Voronoi Diagrams – A survey of a fundamental geometric data structure – Franz Aurenhammer – 1999 – Revue de tous les domaines d'applications (anglais, pdf)

*    Voronoi diagrams (Computational lecture) – Introduction et explication complète de l'algorithme de construction (anglais, pdf)

*    Voronoi DiagramsIndian Statistical Institute – Explication des algorithmes de construction (anglais, pdf)

Cette page

http://villemin.gerard.free.fr/Geometri/Voronoi.htm