Diagrama de Voronoi

En matemáticas , un diagrama de Voronoi es una partición de un plano en regiones cercanas a cada uno de los objetos de un conjunto dado. También se puede clasificar como una teselación . En el caso más simple, estos objetos son un número finito de puntos en el plano (llamados semillas, sitios o generadores). Para cada semilla existe una región correspondiente , llamada celda de Voronoi , que comprende 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 la triangulación de Delaunay de ese conjunto .

El diagrama de Voronoi recibe su nombre del matemático Georgy Voronoy y también se denomina teselación de Voronoi , descomposición de Voronoi , partición de Voronoi o teselación de Dirichlet (en honor a Peter Gustav Lejeune Dirichlet ). Las celdas de Voronoi también se conocen como polígonos de Thiessen , en honor a Alfred H. 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, se nos da un conjunto finito de puntos.${\displaystyle \{p_{1},\dots p_{n}\}}$en el plano euclidiano . En este caso, cada punto${\displaystyle p_{k}}$tiene una celda correspondiente${\displaystyle R_{k}}$que consiste en los puntos del plano euclidiano para los cuales${\displaystyle p_{k}}$es el sitio más cercano: la distancia a${\displaystyle p_{k}}$es menor o igual a la distancia mínima a cualquier otro sitio${\displaystyle p_{j}}$. Para otro sitio${\displaystyle p_{j}}$, los puntos que están más cerca de${\displaystyle p_{k}}$que a${\displaystyle p_{j}}$, o igualmente distantes, forman un semiplano cerrado , cuyo límite es la mediatriz del segmento de recta${\displaystyle p_{j}p_{k}}$. Celúla${\displaystyle R_{k}}$es la intersección de todos estos${\displaystyle n-1}$semi-espacios, y por lo tanto es un polígono convexo . ^{[ 6 ]} Cuando dos celdas en el diagrama de Voronoi comparten un límite, es un segmento de línea , rayo o línea, que consta de todos los puntos en el plano que son equidistantes de sus dos sitios más cercanos. Los vértices del diagrama, donde se encuentran tres o más de estos límites, son los puntos que tienen tres o más sitios más cercanos igualmente distantes.

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

$${\displaystyle R_{k}=\{x\in X\mid d(x,P_{k})\leq d(x,P_{j})\;{\text{para todo}}\;j\neq k\}}$$

El diagrama de Voronoi es simplemente la tupla de celdas.${\textstyle (R_{k})_{k\in K}}$En principio, algunos de los sitios pueden intersecarse e incluso coincidir (más adelante se describe una aplicación para sitios que representan tiendas), pero generalmente se asume que son disjuntos. Además, se permite un número infinito de sitios en la definición (esta configuración tiene aplicaciones en geometría de números y cristalografía ), pero, de nuevo, en muchos casos solo se considera un número finito de sitios.

En el caso particular de un espacio euclidiano de dimensión finita , donde cada sitio es un punto, existe un número finito de puntos y todos son distintos, las celdas de Voronoi son politopos convexos que pueden representarse de forma combinatoria mediante sus vértices, lados, caras bidimensionales, etc. A veces, la estructura combinatoria resultante se denomina diagrama de Voronoi. Sin embargo, en general, las celdas de Voronoi pueden no ser convexas ni estar conectadas.

En el espacio euclidiano usual, podemos reescribir la definición formal en términos usuales. Cada polígono de Voronoi${\textstyle R_{k}}$está asociado con un punto generador ${\textstyle P_{k}}$. Dejar${\textstyle X}$Sea el conjunto de todos los puntos en el espacio euclidiano.${\textstyle P_{1}}$ser un punto que genera su región de Voronoi ${\textstyle R_{1}}$,${\textstyle P_{2}}$que genera ${\textstyle R_{2}}$, y${\textstyle P_{3}}$que genera ${\textstyle R_{3}}$y así sucesivamente. Luego, como lo expresan Tran et al ., ^{[ 7 ]} "todas las ubicaciones en el polígono de Voronoi están más cerca del punto generador de ese polígono que cualquier otro punto generador en el diagrama de Voronoi en el plano euclidiano".

Como ejemplo sencillo, consideremos un grupo de tiendas en una ciudad. Supongamos que queremos estimar el número de clientes de una tienda determinada. Si todo lo demás permanece constante (precio, productos, calidad del servicio, etc.), es razonable suponer que los clientes eligen su tienda preferida simplemente por la distancia: irán a la tienda más cercana. En este caso, la celda de Voronoi${\displaystyle R_{k}}$de una tienda determinada${\displaystyle P_{k}}$Se puede utilizar para dar una estimación aproximada del número de clientes potenciales que acuden a esta tienda (que se modela mediante un punto de nuestra ciudad).

En la mayoría de las ciudades, la distancia entre puntos se puede medir utilizando la conocida distancia euclidiana :

$${\displaystyle \ell _{2}=d\left[\left(a_{1},a_{2}\right),\left(b_{1},b_{2}\right)\right]={\sqrt {\left(a_{1}-b_{1}\right)^{2}+\left(a_{2}-b_{2}\right)^{2}}}}$$

o la distancia de Manhattan :

$${\displaystyle d\left[\left(a_{1},a_{2}\right),\left(b_{1},b_{2}\right)\right]=\left|a_{1}-b_{1}\right|+\left|a_{2}-b_{2}\right|}$$.

Los diagramas de Voronoi correspondientes tienen un aspecto diferente según la métrica de distancia utilizada.

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

distancia euclidiana

Distancia a Manhattan

• El grafo dual de un diagrama de Voronoi (en el caso de un espacio euclidiano con puntos) corresponde a la triangulación de Delaunay para el mismo conjunto de puntos.
• El par más cercano entre los puntos semilla debe encontrarse necesariamente en dos celdas adyacentes en el diagrama de Voronoi.
• Si el escenario es el plano euclidiano y se da un conjunto discreto de puntos, entonces dos puntos del conjunto son adyacentes en la envoltura convexa si y solo si sus celdas de Voronoi comparten un lado infinitamente largo.
• Si el espacio es un espacio normado y se alcanza la distancia a cada sitio (por ejemplo, cuando un sitio es un conjunto compacto o una bola cerrada), entonces cada celda de Voronoi puede representarse como una unión de segmentos de línea que parten de los sitios. ^{[ 8 ]} Como se muestra allí, esta propiedad no necesariamente se cumple cuando no se alcanza la distancia.
• Bajo condiciones relativamente generales (el espacio es un espacio uniformemente convexo de dimensión posiblemente infinita , puede haber infinitos sitios de una forma general, etc.), las celdas de Voronoi poseen una cierta propiedad de estabilidad: un pequeño cambio en la forma de los sitios, por ejemplo, un cambio causado por alguna traslación o distorsión, produce un pequeño cambio en la forma de las celdas de Voronoi. Esta es la estabilidad geométrica de los diagramas de Voronoi. ^{[ 9 ]} Como se muestra allí, esta propiedad no se cumple en general, incluso si el espacio es bidimensional (pero no uniformemente convexo y, en particular, no euclidiano) y los sitios son puntos.

El uso informal de diagramas de Voronoi se remonta a Descartes en 1644. ^{[ 10 ]} Peter Gustav Lejeune Dirichlet utilizó diagramas de Voronoi bidimensionales y tridimensionales en su estudio de formas cuadráticas en 1850. El médico británico John Snow utilizó un diagrama similar a un diagrama de Voronoi en 1854 para ilustrar cómo la mayoría de las personas que murieron en el brote de cólera de Broad Street vivían más cerca de la bomba infectada de Broad Street que de cualquier otra bomba de agua.

Los diagramas de Voronoi reciben su nombre de Georgy Feodosievych Voronoy, quien definió y estudió el caso general n -dimensional en 1908. ^{[ 11 ]} Los diagramas de Voronoi que se utilizan en geofísica y meteorología para analizar datos distribuidos espacialmente se denominan polígonos de Thiessen, en honor al meteorólogo estadounidense Alfred H. Thiessen , quien los utilizó para estimar la precipitación a partir de mediciones dispersas en 1911. Otros nombres equivalentes para este concepto (o casos particulares importantes del mismo): poliedros de Voronoi, polígonos de Voronoi, dominio(s) de influencia, descomposición de Voronoi, teselación(es) de Voronoi, teselación(es) de Dirichlet.

Las teselaciones de Voronoi de redes regulares de puntos en dos o tres dimensiones dan lugar a muchas teselaciones conocidas. Las celdas correspondientes se conocen como celdas de Wigner-Seitz .

• Una red bidimensional produce una teselación de panal irregular, con hexágonos iguales con simetría puntual; en el caso de una red triangular regular, es regular; en el caso de una red rectangular, los hexágonos se reducen a rectángulos en filas y columnas; una red cuadrada produce la teselación regular de cuadrados; cabe señalar que los rectángulos y los cuadrados también pueden generarse mediante otras redes (por ejemplo, la red definida por los vectores (1,0) y (1/2,1/2) produce cuadrados).
• Una red cúbica simple da como resultado un panal cúbico .
• Una red hexagonal compacta da lugar a una teselación del espacio con dodecaedros trapezoidales-rómbicos .
• Una red cúbica centrada en las caras da lugar a una teselación del espacio con dodecaedros rómbicos .
• Una red cúbica centrada en el cuerpo da como resultado una teselación del espacio con octaedros truncados .
• Los planos paralelos con redes triangulares regulares alineadas entre sí por sus centros dan lugar al panal prismático hexagonal .
• Ciertas redes tetragonales centradas en el cuerpo dan lugar a una teselación del espacio con dodecaedros rombohexagonales .

Para el conjunto de puntos ( x , y ) con x en un conjunto discreto X e y en un conjunto discreto Y , obtenemos teselas rectangulares con los puntos no necesariamente en sus centros. 

Si bien una celda de Voronoi normal se define como el conjunto de puntos más cercanos a un único punto en S , una celda de Voronoi de orden n se define como el conjunto de puntos que tienen como vecinos más cercanos a un conjunto particular de n puntos en S. Los diagramas de Voronoi de orden superior también subdividen el espacio.

Los diagramas de Voronoi de orden superior se pueden generar recursivamente. Para generar el diagrama de Voronoi de orden n a partir del conjunto ^S , comience con el diagrama de orden ( ⁿ − 1 ) y reemplace cada celda generada por X = { x ₁ , x ₂ , ..., x _{n −1} } con un diagrama de Voronoi generado en el conjunto S − X .           

Como lo indica la definición, las celdas de Voronoi pueden definirse para métricas distintas a la euclidiana, como la distancia de Mahalanobis o la distancia de Manhattan . Sin embargo, en estos casos, los límites de las celdas de Voronoi pueden ser más complejos que en el caso euclidiano, ya que el lugar geométrico equidistante de dos puntos puede no ser un subespacio de codimensión 1, incluso en el caso bidimensional.

Un diagrama de Voronoi ponderado es aquel en el que la función de un par de puntos para definir una celda de Voronoi es una función de distancia modificada por ponderaciones multiplicativas o aditivas asignadas a los puntos generadores. A diferencia del caso de las celdas de Voronoi definidas mediante una distancia métrica , en este caso algunas de las celdas de Voronoi pueden estar vacías. Un diagrama de potencia es un tipo de diagrama de Voronoi definido a partir de un conjunto de círculos mediante la distancia de potencia ; también puede considerarse como un diagrama de Voronoi ponderado en el que se añade una ponderación definida a partir del radio de cada círculo a la distancia euclidiana al cuadrado desde el centro del círculo. ^{[ 15 ]}

El diagrama de Voronoi de${\displaystyle n}$puntos en${\displaystyle d}$El espacio -dimensional puede tener${\textstyle O(n^{\lceil d/2\rceil })}$vértices, lo que requiere el mismo límite para la cantidad de memoria necesaria para almacenar una descripción explícita de los mismos. Por lo tanto, los diagramas de Voronoi a menudo no son viables para dimensiones moderadas o altas. Una alternativa más eficiente en cuanto a espacio es utilizar diagramas de Voronoi aproximados. ^{[ 16 ]}

Los diagramas de Voronoi también están relacionados con otras estructuras geométricas como el eje medial (que ha encontrado aplicaciones en la segmentación de imágenes, el reconocimiento óptico de caracteres y otras aplicaciones computacionales), el esqueleto recto y los diagramas de zona .

Se conocen varios algoritmos eficientes para construir diagramas de Voronoi, ya sea directamente (como el diagrama en sí) o indirectamente partiendo de una triangulación de Delaunay y obteniendo su dual. Entre los algoritmos directos se incluye el algoritmo de Fortune , un algoritmo de complejidad O ( n log( n )) para generar un diagrama de Voronoi a partir de un conjunto de puntos en un plano. El algoritmo de Bowyer-Watson , un algoritmo de complejidad O ( n log( n )) a O ( n² ⁾ para generar una triangulación de Delaunay en cualquier número de dimensiones, puede utilizarse en un algoritmo indirecto para el diagrama de Voronoi.

Para aproximaciones de cuadrícula discretas (como la representación de píxeles), el algoritmo de inundación de saltos (JFA) y sus variantes se utilizan ampliamente en hardware gráfico comercial ( GPU ). Introducido originalmente por Rong Guodong en 2006, el JFA estándar calcula un diagrama de Voronoi aproximado en${\displaystyle O(\log N)}$pasos paralelos sobre un${\displaystyle N\times N}$cuadrícula. ^{[ 42 ] [ 43 ]} Las optimizaciones posteriores, como la variante aleatoria JFA-star de 2019 introducida por Maciej A. Czyzewski, cambian la complejidad del paso de escalar con la resolución de la cuadrícula al número total de puntos semilla (${\displaystyle n}$), logrando una convergencia más rápida en aproximadamente${\displaystyle O(\log ^{*}n)}$pases. ^{[ 44 ]}

El algoritmo de Lloyd y su generalización mediante el algoritmo de Linde-Buzo-Gray (también conocido como agrupamiento k-means ) utilizan la construcción de diagramas de Voronoi como subrutina. Estos métodos alternan entre pasos en los que se construye el diagrama de Voronoi para un conjunto de puntos semilla y pasos en los que estos puntos se mueven a nuevas ubicaciones más centrales dentro de sus celdas. Estos métodos pueden utilizarse en espacios de dimensión arbitraria para converger iterativamente hacia una forma especializada del diagrama de Voronoi, denominada teselación de Voronoi centroidal , donde los puntos se han movido a ubicaciones que también son los centros geométricos de sus celdas.

Las mallas de Voronoi también se pueden generar en 3D.

• 
  Puntos aleatorios en 3D para formar una partición de Voronoi en 3D.
• 
  Malla de Voronoi 3D de 25 puntos aleatorios
• 
  Malla de Voronoi 3D de 25 puntos aleatorios con 0,3 de opacidad y puntos
• 
  Malla de Voronoi 3D de 25 piezas poliédricas convexas de puntos aleatorios

• Weisstein, Eric W. "Diagrama de Voronoi" . MundoMatemático .
• Diagramas de Voronoi en CGAL , la biblioteca de algoritmos de geometría computacional.
• Programa de demostración para el algoritmo SFTessellation, que crea un diagrama de Voronoi utilizando un modelo de incendios esteparios.