diagrama de Voronoi

En matemáticas , un diagrama de Voronoi es una partición de un plano en regiones cercanas a cada uno de un conjunto dado de objetos. En el caso más simple, estos objetos son solo un número finito de puntos en el plano (llamados semillas, sitios o generadores). Para cada semilla hay una región correspondiente , llamada celda de Voronoi , que consta de todos los puntos del plano más cercanos a esa semilla que a cualquier otra. El diagrama de Voronoi de un conjunto de puntos es dual a su triangulación de Delaunay .

El diagrama de Voronoi lleva el nombre de Georgy Voronoy , y también se llama teselado de Voronoi, descomposición de Voronoi, partición de Voronoi o teselado de Dirichlet (en honor a Peter Gustav Lejeune Dirichlet ). Las celdas de Voronoi también se conocen como polígonos de Thiessen . ^{[1] [2] [3]} Los diagramas de Voronoi tienen aplicaciones prácticas y teóricas en muchos campos, principalmente en ciencia y tecnología , pero también en artes visuales . ^{[4] [5]}

En el caso más simple, que se muestra en la primera imagen, tenemos un conjunto finito de puntos { p ₁ , ..., p _n } en el plano euclidiano . En este caso, cada sitio p _k es simplemente un punto, y su correspondiente celda de Voronoi R _k consta de cada punto en el plano euclidiano cuya distancia a p _k es menor o igual que su distancia a cualquier otro p _k . Cada una de esas celdas se obtiene de la intersección de semiespacios y , por lo tanto, es un poliedro (convexo) . ^[6] Los segmentos de líneadel diagrama de Voronoi son todos los puntos en el plano que son equidistantes a los dos sitios más cercanos. Los vértices ( nodos ) de Voronoi son los puntos equidistantes a tres (o más) sitios.

Sea un espacio métrico con función de distancia . Sea un conjunto de índices y sea ​​una tupla (colección ordenada) de subconjuntos no vacíos (los sitios) en el espacio . La celda de Voronoi, o región de Voronoi , asociada con el sitio es el conjunto de todos los puntos en cuya distancia a no es mayor que su distancia a los otros sitios , donde cualquier índice es diferente de . En otras palabras, si denota la distancia entre el punto y el subconjunto , entonces${\ estilo de texto X}$${\ estilo de texto d}$${\ estilo de texto K}$${\textstyle (P_{k})_{k\in K}}$${\ estilo de texto X}$${\ estilo de texto R_ {k}}$${\ estilo de texto P_{k}}$${\ estilo de texto X}$${\ estilo de texto P_{k}}$${\ estilo de texto P_ {j}}$${\ estilo de texto j}$${\ estilo de texto k}$${\textstyle d(x,\,A)=\inf\{d(x,\,a)\mid a\in A\}}$${\ estilo de texto x}$${\ estilo de texto A}$

20 puntos y sus celdas Voronoi (versión más grande a continuación )

Diagramas de Voronoi de 20 puntos bajo dos métricas diferentes

distancia entre manhattan

Esta es una porción del diagrama de Voronoi de un conjunto aleatorio de puntos en un cuadro 3D. En general, una sección transversal de una teselación de Voronoi 3D no es una teselación de Voronoi 2D en sí misma. (Las celdas son todas poliedros convexos ) .

Diagrama de Voronoi aproximado de un conjunto de puntos. Observe los colores combinados en el límite borroso de las celdas de Voronoi.

Una teselación de Voronoi emerge por crecimiento radial desde las semillas hacia el exterior.