Diagrama de Voronoi

Ajustar Compartir Imprimir Citar

Tipo de partición de plano

20 puntos y sus células Voronoi (versión más grande abajo)

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 la triangulación de Delaunay de ese conjunto.

El diagrama de Voronoi lleva el nombre del matemático Georgy Voronoy, y también se llama teselado de Voronoi, descomposición de Voronoi, partición de Voronoi, o un teselado de Dirichlet (después de Peter Gustav Lejeune Dirichlet). Las celdas de Voronoi también se conocen como polígonos de Thiessen. 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.

El caso más simple

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 consiste en cada punto en el plano euclidiano cuya distancia a p_k es menor o igual a 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). Los segmentos de línea del diagrama de Voronoi son todos los puntos en el plano que son equidistantes de los dos sitios más cercanos. Los vértices (nodos) de Voronoi son los puntos equidistantes a tres (o más) sitios.

Definición formal

Vamos ${textstyle X}$ ser un espacio métrico con función de distancia ${textstyle d}$ . Vamos ${textstyle K}$ ser un conjunto de índices y dejar ${textstyle (P_{k})_{kin K}}$ ser un tuple (recopilación indexada) de subconjuntos no vacíos (los sitios) en el espacio ${textstyle X}$ . La célula 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 ${textstyle P_{k}}$ no es mayor que su distancia a los otros sitios ${textstyle P_{j}}$ , donde ${textstyle j}$ es cualquier índice diferente de ${textstyle k}$ . En otras palabras, si ${textstyle d(x,,A)=inf{d(x,,a)mid ain A}}$ denota la distancia entre el punto ${textstyle x}$ y el subconjunto ${textstyle A}$ , entonces

{displaystyle R_{k}={xin Xmid d(x,P_{k})leq d(x,P_{j});{text{for all}};jneq k}}

El diagrama Voronoi es simplemente el tuple de células ${textstyle (R_{k})_{kin K}}$ . En principio, algunos de los sitios pueden interseccionar e incluso coincidir (una aplicación se describe a continuación para sitios que representan tiendas), pero generalmente se supone que están descompuestos. Además, se permiten infinitamente muchos 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 sólo se consideran finitos muchos sitios.

En el caso particular donde el espacio es un espacio euclidiano de dimensión finita, cada sitio es un punto, hay un número finito de puntos y todos son diferentes, entonces las celdas de Voronoi son politopos convexos y se pueden representar en un forma combinatoria utilizando sus vértices, lados, caras bidimensionales, etc. A veces, la estructura combinatoria inducida se denomina diagrama de Voronoi. Sin embargo, en general, las celdas de Voronoi pueden no ser convexas o incluso conectadas.

En el espacio habitual de Euclidean, podemos reescribir la definición formal en términos habituales. Cada polígono Voronoi ${textstyle R_{k}}$ se asocia con un punto generador ${textstyle P_{k}}$ . Vamos ${textstyle X}$ ser el conjunto de todos los puntos en el espacio Euclideano. Vamos ${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. Entonces, como lo expresó Tran et, "todas las ubicaciones en el polígono Voronoi están más cerca del punto generador de ese polígono que cualquier otro punto generador en el diagrama Voronoi en el plano Euclideano".

Ilustración

Como ilustración simple, considere un grupo de tiendas en una ciudad. Supongamos que queremos estimar el número de clientes de una tienda dada. Con todo lo demás siendo igual (precio, productos, calidad de servicio, etc.), es razonable suponer que los clientes eligen su tienda preferida simplemente por consideraciones de distancia: irán a la tienda ubicada más cercana a ellos. En este caso la célula Voronoi $R_{k}$ de una tienda dada $P_k$ se puede utilizar para dar una estimación aproximada del número de clientes potenciales que van a esta tienda (que es modelado por un punto en nuestra ciudad).

Para la mayoría de las ciudades, la distancia entre puntos se puede medir usando el conocido Distancia euclidiana:

ell_2 = dleft[left(a_1, a_2right), left(b_1, b_2right)right] = sqrt{left(a_1 - b_1right)^2 + left(a_2 - b_2right)^2}

o la distancia de Manhattan:

dleft[left(a_1, a_2right), left(b_1, b_2right)right] = left|a_1 - b_1right| + left|a_2 - b_2right|

Los diagramas de Voronoi correspondientes se ven diferentes para diferentes métricas de distancia.

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

Distancia euroclidiana

Distancia a Manhattan

Propiedades

El gráfico dual para un diagrama Voronoi (en el caso de un espacio euclidiano con puntos) corresponde a la triangulación Delaunay para el mismo conjunto de puntos.
El par más cercano de puntos corresponde a dos células adyacentes en el diagrama Voronoi.
Supongamos que el ajuste es el plano Euclideano y se da un conjunto discreto de puntos. Luego dos puntos del conjunto están adyacentes en el casco convexo si y sólo si sus células Voronoi comparten un lado infinitamente largo.
Si el espacio es un espacio normalizado y la distancia a cada sitio se alcanza (por ejemplo, cuando un sitio es un conjunto compacto o una bola cerrada), entonces cada célula Voronoi puede ser representado como una unión de segmentos de línea que emanan de los sitios. Como se muestra allí, esta propiedad no se mantiene necesariamente cuando la distancia no se alcanza.
En condiciones relativamente generales (el espacio es un espacio uniformemente convexo posiblemente infinito, puede haber infinitamente muchos sitios de forma general, etc.) Las células Voronoi disfrutan de una cierta propiedad de estabilidad: un pequeño cambio en las formas de los sitios, por ejemplo, un cambio causado por alguna traducción o distorsión, produce un pequeño cambio en la forma de las células Voronoi. Esta es la estabilidad geométrica de los diagramas de Voronoi. Como se muestra allí, esta propiedad no se mantiene en general, incluso si el espacio es bidimensional (pero no-uniformly convex, y, en particular, no-Euclidean) y los sitios son puntos.

Historia e investigación

El uso informal de los diagramas de Voronoi se remonta a Descartes en 1644. Peter Gustav Lejeune Dirichlet usó diagramas de Voronoi bidimensionales y tridimensionales en su estudio de formas cuadráticas en 1850. El médico británico John Snow usó un diagrama similar al 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 llevan el nombre de Georgy Feodosievych Voronoy, quien definió y estudió el caso general n-dimensional en 1908. Los diagramas de Voronoi que se utilizan en geofísica y meteorología para analizar datos distribuidos espacialmente (como mediciones de lluvia) se llaman polígonos de Thiessen en honor al meteorólogo estadounidense Alfred H. Thiessen. 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, teselado(s) de Voronoi, teselado(s) de Dirichlet.

Ejemplos

Esta es una rebanada del diagrama Voronoi de un conjunto aleatorio de puntos en una caja 3D. En general, una sección transversal de un tessellation Voronoi 3D no es una tessellation 2D Voronoi en sí. (Las células son convexas polihedra.)

Las teselaciones de Voronoi de redes regulares de puntos en dos o tres dimensiones dan lugar a muchas teselaciones familiares.

La rejilla 2D da una tessellación irregular de panal, con hexágonos iguales con simetría de puntos; en el caso de una rejilla triangular regular es regular; en el caso de una rejilla rectangular los hexágonos reducen a rectángulos en filas y columnas; una rejilla cuadrada da la tessellación regular de cuadrados; nota que los rectángulos y los cuadrados también se pueden definir por medio cordones
Una simple rejilla cúbica da el panal cúbico.
Una celosía hexagonal de cerca da una tessellación de espacio con trapezo-rhombic dodecahedra.
Una celosía cúbica centrada en la cara da una tessellation del espacio con dodecahedra rhombic.
Una celosía cúbica centrada en el cuerpo da una tessellación de espacio con octahedra truncada.
Los aviones paralelos con rejas triangulares regulares alineadas con los centros del otro dan el panal hexagonal prismático.
Algunas celosías tetragonales centradas en el cuerpo dan una tessellación de espacio con rombo-hexagonal dodecahedra.

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

Diagramas de Voronoi de orden superior

Aunque 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 nésimo orden se define como el conjunto de puntos que tienen un conjunto particular de n puntos en S como sus n vecinos más cercanos. 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^th a partir del conjunto S, comience con (n − 1)th-order y reemplace cada celda generada por X = {x₁, x₂,..., x_n−1} con un diagrama de Voronoi generado en el conjunto S − X.

Diagrama de Voronoi del punto más lejano

Para un conjunto de n puntos, el diagrama de Voronoi de (n − 1)^ésimo orden se denomina diagrama de Voronoi del punto más lejano.

Para un conjunto dado de puntos S = {p₁, p₂,..., p_n} el diagrama de Voronoi del punto más lejano divide el plano en celdas en las que el mismo punto de P es el punto más lejano. Un punto de P tiene una celda en el diagrama de Voronoi del punto más lejano si y solo si es un vértice del casco convexo de P. Sea H = {h₁, h₂,..., h_k} sea el casco convexo de P; entonces el diagrama de Voronoi del punto más lejano es una subdivisión del plano en celdas k, una para cada punto en H, con la propiedad de que un punto q se encuentra en la celda correspondiente a un sitio h_i si y solo si d(q, h_i) > d(q, p_j) para cada p_j ∈ S con h_i ≠ p_j, donde d(p, q) es la distancia euclidiana entre dos puntos p y q.

Los límites de las celdas en el diagrama de Voronoi del punto más lejano tienen la estructura de un árbol topológico, con infinitos rayos como hojas. Todo árbol finito es isomorfo al árbol formado de esta manera a partir de un diagrama de Voronoi del punto más lejano.

Generalizaciones y variaciones

Como implica la definición, las celdas de Voronoi se pueden definir para métricas distintas a las euclidianas, 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 complicados que en el caso euclidiano, ya que el lugar geométrico equidistante de dos puntos puede no ser subespacio de codimensión 1, incluso en el caso bidimensional.

Diagrama de Voronoi aproximado de un conjunto de puntos. Observe los colores mezclados en el límite borroso de las células Voronoi.

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 pesos multiplicativos o aditivos asignados a los puntos generadores. A diferencia del caso de las celdas de Voronoi definidas mediante una distancia que es una 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 utilizando la distancia de potencia; también se puede considerar como un diagrama de Voronoi ponderado en el que se suma un peso definido a partir del radio de cada círculo a la distancia euclidiana al cuadrado desde el centro del círculo.

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

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 informáticas), el esqueleto recto y los diagramas de zonas.

Aplicaciones

Meteorología/Hidrología

Se utiliza en meteorología e hidrología de ingeniería para encontrar los pesos de los datos de precipitación de las estaciones sobre una zona (aguantada). Los puntos que generan los polígonos son la estación que registra datos de precipitación. Los bisectores perpendiculares se dibujan en la línea que une cada dos estaciones. Esto resulta en la formación de polígonos alrededor de las estaciones. La zona $(A_{i})$ punto de la estación de contacto se conoce como área de influencia de la estación. La precipitación promedio se calcula por la fórmula ${displaystyle {bar {P}}={frac {sum A_{i}P_{i}}{sum A_{i}}}}$

Humanidades y ciencias sociales

En la arqueología clásica, específicamente la historia del arte, se analiza la simetría de las cabezas de estatuas para determinar el tipo de estatua que podría haber pertenecido una cabeza cortada. Un ejemplo de esto que hizo uso de células Voronoi fue la identificación de la cabeza de Sabouroff, que hizo uso de una malla de polígono de alta resolución.
En dialectometría, las células Voronoi se utilizan para indicar una supuesta continuidad lingüística entre los puntos de encuesta.
En la ciencia política, los diagramas Voronoi se han utilizado para estudiar la competencia multidimensional y multipartidista.

Ciencias naturales

Una tessellación Voronoi emerge por el crecimiento radial de las semillas hacia fuera.

En biología, los diagramas de Voronoi se utilizan para modelar una serie de estructuras biológicas diferentes, incluyendo células y microarquitectura ósea. De hecho, las tesselaciones de Voronoi funcionan como una herramienta geométrica para comprender las limitaciones físicas que impulsan la organización de los tejidos biológicos.
En hidrología, los diagramas de Voronoi se utilizan para calcular la precipitación de un área, basado en una serie de mediciones de puntos. En este uso, generalmente se denominan poligones Thiessen.
En la ecología, los diagramas de Voronoi se utilizan para estudiar los patrones de crecimiento de los bosques y los canopies forestales, y también pueden ser útiles para desarrollar modelos predictivos para incendios forestales.
En la química computacional, los sitios ligando se transforman en diagramas Voronoi para aplicaciones de aprendizaje automático (por ejemplo, clasificar los bolsillos de unión en proteínas). En otras aplicaciones, las células Voronoi definidas por las posiciones de los núcleos en una molécula se utilizan para calcular los cargos atómicos. Esto se hace utilizando el método de densidad de deformación Voronoi.
En la astrofísica, los diagramas Voronoi se utilizan para generar zonas de aislamiento adaptativo en imágenes, agregando flujos de señal en cada uno. El objetivo principal de estos procedimientos es mantener una relación de señal a ruido relativamente constante en todas las imágenes.
En la dinámica de fluidos computacionales, la tessellación Voronoi de un conjunto de puntos se puede utilizar para definir los dominios computacionales utilizados en métodos de volumen finitos, por ejemplo, como en el código cosmológico de malla móvil AREPO.
En física computacional, los diagramas de Voronoi se utilizan para calcular los perfiles de un objeto con Shadowgraph y radiografía proton en física de alta densidad energética.

Salud

En el diagnóstico médico, se pueden utilizar modelos de tejido muscular basados en diagramas Voronoi para detectar enfermedades neuromusculares.
En epidemiología, los diagramas de Voronoi se pueden utilizar para correlacionar las fuentes de infecciones en epidemias. Una de las primeras aplicaciones de los diagramas de Voronoi fue implementada por John Snow para estudiar el brote de cólera de la calle Broad Street en Soho, Inglaterra. Mostró la correlación entre zonas residenciales en el mapa del centro de Londres cuyos residentes habían estado utilizando una bomba de agua específica, y las zonas con más muertes debido al brote.

Ingeniería

En la física polímero, los diagramas Voronoi se pueden utilizar para representar volúmenes libres de polímeros.
En la ciencia de materiales, las microestructuras policristalinas en aleaciones metálicas están representadas comúnmente usando tessellations Voronoi. En el crecimiento de la isla, el diagrama Voronoi se utiliza para estimar la tasa de crecimiento de las islas individuales. En física de estado sólido, la célula Wigner-Seitz es la tessellación Voronoi de un sólido, y la zona Brillouin es la tessellación Voronoi del espacio recíproco (número de onda) de cristales que tienen la simetría de un grupo espacial.
En la aviación, los diagramas de Voronoi se superponen en los diagramas oceánicos para identificar el aeródromo más cercano para la desviación en vuelo (véase ETOPS), ya que un avión avanza a través de su plan de vuelo.
En la arquitectura, los patrones de Voronoi fueron la base para la entrada ganadora para el redesarrollo de The Arts Centre Gold Coast.
En la planificación urbana, los diagramas de Voronoi se pueden utilizar para evaluar el sistema de Zona de carga de carga.
En la minería, los poligones de Voronoi se utilizan para estimar las reservas de materiales valiosos, minerales u otros recursos. Los taladros exploratorios se utilizan como el conjunto de puntos en los polígonos Voronoi.
En la metrología superficial, la tessellación Voronoi se puede utilizar para modelar la rugosidad superficial.
En robótica, algunas de las estrategias de control y algoritmos de planificación de caminos de sistemas multi-robot se basan en la partición Voronoi del medio ambiente.

Geometría

Una estructura de datos de localización de puntos se puede construir en la parte superior del diagrama Voronoi para responder a consultas vecinas más cercanas, donde se quiere encontrar el objeto más cercano a un punto de consulta dado. Las consultas más cercanas tienen numerosas aplicaciones. Por ejemplo, uno podría querer encontrar el hospital más cercano o el objeto más similar en una base de datos. Una gran aplicación es la cuantificación vectorial, comúnmente utilizada en la compresión de datos.
En geometría, los diagramas de Voronoi se pueden utilizar para encontrar el círculo vacío más grande en medio de un conjunto de puntos, y en un polígono encerrado; por ejemplo, para construir un nuevo supermercado lo más lejos posible de todos los existentes, acostado en una determinada ciudad.
Los diagramas Voronoi junto con los diagramas Voronoi de punto más lejano se utilizan para algoritmos eficientes para calcular la redondez de un conjunto de puntos. El enfoque Voronoi también se utiliza en la evaluación de la circularidad/redondez al evaluar el conjunto de datos desde una máquina de medición de coordenadas.

Informática

En redes, los diagramas Voronoi se pueden utilizar en derivaciones de la capacidad de una red inalámbrica.
En los gráficos de la computadora, los diagramas de Voronoi se utilizan para calcular los patrones de geometría de fractura 3D / fracturación. También se utiliza para generar texturas orgánicas o de aspecto de lava.
En la navegación autónoma del robot, los diagramas Voronoi se utilizan para encontrar rutas claras. Si los puntos son obstáculos, entonces los bordes del gráfico serán las rutas más alejadas de los obstáculos (y teóricamente cualquier colisión).
En el aprendizaje automático, los diagramas Voronoi se utilizan para hacer clasificaciones de 1-NN.
En la reconstrucción de escena global, incluso con sitios de sensores aleatorios y flujo de vela inestable, datos geofísicos y datos de turbulencia 3D, las tesselaciones Voronoi se utilizan con aprendizaje profundo.
En el desarrollo de la interfaz de usuario, los patrones de Voronoi se pueden utilizar para calcular el mejor estado de la palanca para un punto dado.

Cívica y planificación

En Melbourne, los estudiantes de la escuela pública siempre son elegibles para asistir a la escuela primaria o secundaria más cercana a donde viven, según se mide por una distancia directa. Por lo tanto, el mapa de las zonas escolares es un diagrama Voronoi.

Panadería

El chef de pastelería ucraniano Dinara Kasko utiliza los principios matemáticos del diagrama Voronoi para crear moldes de silicona hechos con una impresora 3D para formar sus pasteles originales.

Algoritmos

Se conocen varios algoritmos eficientes para construir diagramas de Voronoi, ya sea directamente (como el propio diagrama) o indirectamente comenzando con una triangulación de Delaunay y luego obteniendo su dual. Los algoritmos directos incluyen el algoritmo de Fortune, un algoritmo O(n log(n)) para generar un diagrama de Voronoi a partir de un conjunto de puntos en un plano. Algoritmo Bowyer-Watson, un algoritmo O(n log(n)) a O(n²) para generar una triangulación de Delaunay en cualquier número de dimensiones, se puede utilizar en un algoritmo indirecto para el diagrama de Voronoi. El algoritmo de inundación de salto puede generar diagramas de Voronoi aproximados en tiempo constante y es adecuado para su uso en hardware de gráficos básicos.

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

Voronoi en 3D

Las mallas de Voronoi también se pueden generar en 3D. Mathematica 13.1 agregó soporte para renderizar descomposiciones de espacio en malla Voronoi 3D.

Puntos aleatorios en 3D para formar una partición Voronoi 3D.
3D Voronoi malla de 25 puntos al azar.
3D Voronoi malla de 25 puntos al azar con 0,3 opacidad y puntos
Mesh 3D Voronoi de 25 puntos aleatorios convexos piezas de polihedra.