Voronoi diagram

Voronoi diagram

Diagramme de Voronoï

Un diagramme de Voronoï.

En mathématiques, un diagramme de Voronoï (aussi appelé décomposition de Voronoï, partition de Voronoï ou encore polygones de Voronoï) représente une décomposition particulière d’un espace métrique déterminée par les distances à un ensemble discret d’objets de l’espace, en général un ensemble discret de points. Il doit son nom au mathématicien russe Georgi Fedoseevich Voronoï (1868 - 1908).

Sommaire

Définition

On se place dans un espace euclidien E. Soit S un ensemble fini 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 autre point de S.

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

Pour deux points a et b de S, l’ensemble Π(a,b) des points équidistants de a et b est un hyperplan affine (un sous-espace affine de co-dimension 1). Cet hyperplan est la frontière entre l’ensemble des points plus proches 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.

Fichier:Voronoi.png
Construction du diagramme de Voronoï en 2D

En dimension 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 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 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 de l'ensemble.

Le diagramme de Voronoï est le dual de la triangulation de Delaunay, on peut définir la triangulation de Delaunay à partir du diagramme de Voronoï, deux points p et q créent une arête dans le graphe 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 médecin 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 de Soho vivait plus près de la pompe infectée de Broad Street que de n’importe quelle autre pompe.

Les diagrammes de Voronoï portent le nom du mathématicien 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 pour analyser des données 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 : Exemple de diagramme de Voronoï.png

Algorithmes

L'algorithme de Steven Fortune (1987, Laboratoires Bell AT&T), démontré comme asymptotiquement optimal, permet de calculer le diagramme de Voronoï d'un ensemble de n points du plan dans le temps 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 par exemple.
  • Effet de Mosaïque dans un logiciel de retouche d'image.
  • Construction d'un dôme géodésique dual
  • Partition des structures spatiales des populations d'étoiles.
  • Diagnostic de cellules cancéreuses.
  • Modélisation de microstructures telles que certains aciers.
  • Simulation de la circulation des fluides dans les milieux poreux.
  • Calculs de trajectoire en robotique mobile.
  • ...

Références

  • Steven Fortune, "A Sweepline Algorithm for Voronoi Diagrams", Algorithmica, volume 2, 1987, pp. 153-174

Liens externes

  • Portail de la géométrie Portail de la géométrie
  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Diagramme de Vorono%C3%AF ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Voronoi diagram de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Voronoi diagram — The Voronoi diagram of a random set of points in the plane (all points lie within the image). In mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified… …   Wikipedia

  • Voronoi diagram — noun A diagram that assigns a set of points in a plane into an equal number of cells, such that each point p is inside a cell consisting of all regions closer to p than to any other point …   Wiktionary

  • Voronoi diagram — …   Deutsch Wikipedia

  • Voronoi-Diagramm — Als Voronoi Diagramm, auch Thiessen Polygonen oder Dirichlet Zerlegung, wird eine Zerlegung des Raumes in Regionen bezeichnet, die durch eine vorgegebene Menge an Punkten des Raumes, hier als Zentren bezeichnet, bestimmt werden. Jede Region wird… …   Deutsch Wikipedia

  • Voronoi-Interpolation — Die Voronoi Interpolation (engl. natural neighbor interpolation „Interpolation durch natürliche Nachbarn“), auch Sibson Interpolation genannt, ist ein Interpolationsverfahren, das mit Voronoi Diagrammen arbeitet. Prinzip Gegeben sind Punkte in… …   Deutsch Wikipedia

  • Diagram — Further information: Chart Sample flowchart representing the decision process to add a new article to Wikipedia. A diagram is a two dimensional geometric symbolic representation of information according to some visualization technique. Sometimes …   Wikipedia

  • Mathematical diagram — This article is about general diagrams in mathematics. For diagrams in the category theoretical sense, see Diagram (category theory). Euclid s Elements, ms. from Lüneburg, A.D. 1200 Mathematical diagrams are diagrams in the field of mathematics,… …   Wikipedia

  • Fortune's algorithm — is a plane sweep algorithm for generating a Voronoi diagram from a set of points in a plane using O( n log n ) time and O( n ) space. [cite book|author = Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf | year = 2000 | title …   Wikipedia

  • Delaunay triangulation — A Delaunay triangulation in the plane with circumcircles shown In mathematics and computational geometry, a Delaunay triangulation for a set P of points in the plane is a triangulation DT(P) such that no point in P is inside the circumcircle of… …   Wikipedia

  • Lloyd's algorithm — In computer graphics and electrical engineering, Lloyd s algorithm, also known as Voronoi iteration or relaxation, is a method for evenly distributing samples or objects, usually points.Lloyd s algorithm starts with an initial distribution of… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”