Diagrama de Voronoi

Tipo de partición plana

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

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 simplemente 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 consiste en 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 le 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]}

El caso más simple

En el caso más simple, que se muestra en la primera imagen, se nos da un conjunto finito de puntos en el plano euclidiano . En este caso, cada sitio es uno de estos puntos dados, y su celda de Voronoi correspondiente consiste en cada punto en el plano euclidiano para el cual es el sitio más cercano: la distancia a es menor o igual que la distancia mínima a cualquier otro sitio . Para otro sitio , los puntos que están más cerca de que a , o igualmente distantes, forman un semiespacio cerrado , cuyo límite es la bisectriz perpendicular del segmento de línea . La celda es la intersección de todos estos semiespacios 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 consiste en todos los puntos en el plano que son equidistantes a 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. ${\displaystyle \{p_{1},\dots p_{n}\}}$ ${\displaystyle p_{k}}$ ${\displaystyle R_{k}}$ ${\displaystyle p_{k}}$ ${\displaystyle p_{k}}$ ${\displaystyle p_{j}}$ ${\displaystyle p_{j}}$ ${\displaystyle p_{k}}$ ${\displaystyle p_{j}}$ ${\displaystyle p_{j}p_{k}}$ ${\displaystyle R_{k}}$ ${\displaystyle n-1}$

Definición formal

Sea un espacio métrico con función de distancia . Sea un conjunto de índices y sea una tupla (colección indexada) 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 cuya distancia a no es mayor que su distancia a los otros sitios , donde es cualquier índice diferente de . En otras palabras, si denota la distancia entre el punto y el subconjunto , entonces ${\textstyle X}$ ${\textstyle d}$ ${\textstyle K}$ ${\textstyle (P_{k})_{k\in K}}$ ${\textstyle X}$ ${\textstyle R_{k}}$ ${\textstyle P_{k}}$ ${\textstyle X}$ ${\textstyle P_{k}}$ ${\textstyle P_{j}}$ ${\textstyle j}$ ${\textstyle k}$ ${\textstyle d(x,\,A)=\inf\{d(x,\,a)\mid a\in A\}}$ ${\textstyle x}$ ${\textstyle A}$

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

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

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

En el espacio euclidiano habitual, podemos reescribir la definición formal en términos habituales. Cada polígono de Voronoi está asociado a un punto generador . Sea el conjunto de todos los puntos en el espacio euclidiano. Sea un punto que genera su región de Voronoi , que genera , y que genera , y así sucesivamente. Entonces, como lo expresaron 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". ${\textstyle R_{k}}$ ${\textstyle P_{k}}$ ${\textstyle X}$ ${\textstyle P_{1}}$ ${\textstyle R_{1}}$ ${\textstyle P_{2}}$ ${\textstyle R_{2}}$ ${\textstyle P_{3}}$ ${\textstyle R_{3}}$

Ilustración

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

Para 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 se ven diferentes para diferentes métricas de distancia.

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

Propiedades

• El gráfico dual de un diagrama de Voronoi (en el caso de un espacio euclidiano con sitios puntuales) corresponde a la triangulación de Delaunay para el mismo conjunto de puntos.
• El par de puntos más cercano corresponde a dos celdas adyacentes en el diagrama de Voronoi.
• Supongamos que el escenario es el plano euclidiano y que 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 emanan de los sitios. ^[8] Como se muestra allí, esta propiedad no se cumple necesariamente cuando no se alcanza la distancia.
• En condiciones relativamente generales (el espacio es un espacio uniformemente convexo posiblemente de dimensión infinita , puede haber infinitos sitios de una forma general, etc.) las celdas de 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 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.

Historia e investigación

El uso informal de los 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 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 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 las precipitaciones 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, teselaciones de Voronoi, teselaciones de Dirichlet.

Ejemplos

Esta es una sección transversal del diagrama de Voronoi de un conjunto aleatorio de puntos en una caja 3D. En general, una sección transversal de una teselación de Voronoi 3D es un diagrama de potencia , una forma ponderada de un diagrama de Voronoi 2D, en lugar de ser un diagrama de Voronoi no ponderado.

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

• Una red 2D da una teselación irregular en forma de panal, 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 da la teselación regular de cuadrados; nótese que los rectángulos y los cuadrados también pueden ser generados por otras redes (por ejemplo, la red definida por los vectores (1,0) y (1/2,1/2) da 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 lugar a una teselación del espacio con octaedros truncados .
• Los planos paralelos con redes triangulares regulares alineadas entre sí dan como resultado el panal prismático hexagonal .
• Ciertas redes tetragonales centradas en el cuerpo dan una teselación del espacio con dodecaedros rombohexagonales .

Ciertas redes tetragonales centradas en el cuerpo dan 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 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 orden n se define como el conjunto de puntos que tiene 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 de forma recursiva. 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 .

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 de punto más lejano.

Para un conjunto dado de puntos S  = { p ₁ ,  p ₂ , ...,  p _n } el diagrama de Voronoi de 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 de punto más lejano si y solo si es un vértice de la envoltura convexa de P . Sea H  = { h ₁ ,  h ₂ , ...,  h _k } la envoltura convexa de P ; entonces el diagrama de Voronoi de punto más lejano es una subdivisión del plano en k celdas, 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 . ^{[12] [13]}

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

Generalizaciones y variaciones

Como se desprende de la definición, las celdas de Voronoi pueden definirse para métricas distintas de 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 complicados 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.

Diagrama de Voronoi aproximado de un conjunto de puntos. Observe los colores mezclados en el límite difuso de las celdas de 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 utilizando 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 potencia de la distancia ; también puede considerarse como un diagrama de Voronoi ponderado en el que un peso definido a partir del radio de cada círculo se suma a la distancia euclidiana al cuadrado desde el centro del círculo. ^[15]

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

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 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 un área (cuenca hidrográfica). Los puntos que generan los polígonos son las distintas estaciones que registran los datos de precipitación. Las bisectrices perpendiculares se dibujan a la línea que une dos estaciones cualesquiera. Esto da como resultado la formación de polígonos alrededor de las estaciones. El área que toca el punto de la estación se conoce como área de influencia de la estación. La precipitación promedio se calcula mediante la fórmula ${\displaystyle (A_{i})}$ ${\displaystyle {\bar {P}}={\frac {\sum A_{i}P_{i}}{\sum A_{i}}}}$

Humanidades y ciencias sociales

• En la arqueología clásica , específicamente en la historia del arte , se analiza la simetría de las cabezas de las estatuas para determinar a qué tipo de estatua puede haber pertenecido una cabeza cortada. Un ejemplo de esto que hizo uso de celdas de Voronoi fue la identificación de la cabeza de Sabouroff , que hizo uso de una malla poligonal de alta resolución . ^{[17] [18]}
• En dialectometría , las células de Voronoi se utilizan para indicar una supuesta continuidad lingüística entre puntos de estudio.
• En ciencias políticas , los diagramas de Voronoi se han utilizado para estudiar la competencia multidimensional y multipartidista. ^[19]

Ciencias naturales

Una teselación de Voronoi surge por crecimiento radial desde las semillas hacia afuera.

• En biología , los diagramas de Voronoi se utilizan para modelar una serie de estructuras biológicas diferentes, incluidas las células ^[20] y la microarquitectura ósea. ^[21] De hecho, las teselaciones de Voronoi funcionan como una herramienta geométrica para comprender las restricciones físicas que impulsan la organización de los tejidos biológicos. ^[22]
• En hidrología , los diagramas de Voronoi se utilizan para calcular la pluviosidad de una zona a partir de una serie de mediciones puntuales. En este contexto, se los suele denominar polígonos de Thiessen.
• En ecología , los diagramas de Voronoi se utilizan para estudiar los patrones de crecimiento de los bosques y las copas de los árboles, y también pueden ser útiles para desarrollar modelos predictivos de incendios forestales.
• En etología , los diagramas de Voronoi se utilizan para modelar dominios de peligro en la teoría de la manada egoísta .
• En química computacional , los sitios de unión de ligandos se transforman en diagramas de Voronoi para aplicaciones de aprendizaje automático (por ejemplo, para clasificar los bolsillos de unión en proteínas). ^[23] En otras aplicaciones, las celdas de Voronoi definidas por las posiciones de los núcleos en una molécula se utilizan para calcular cargas atómicas . Esto se hace utilizando el método de densidad de deformación de Voronoi .
• En astrofísica , los diagramas de Voronoi se utilizan para generar zonas de suavizado adaptativo en las imágenes, añadiendo flujos de señal en cada una de ellas. El objetivo principal de estos procedimientos es mantener una relación señal-ruido relativamente constante en todas las imágenes.
• En dinámica de fluidos computacional , la teselación de Voronoi de un conjunto de puntos se puede utilizar para definir los dominios computacionales utilizados en métodos de volumen finito , por ejemplo, como en el código de cosmología de malla móvil AREPO. ^[24]
• En física computacional , los diagramas de Voronoi se utilizan para calcular perfiles de un objeto con Shadowgraph y radiografía de protones en física de alta densidad de energía . ^[25]

Salud

• En el diagnóstico médico , se pueden utilizar modelos de tejido muscular, basados ​​en diagramas de Voronoi, para detectar enfermedades neuromusculares. ^[22]
• 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 Broad Street en Soho, Inglaterra, en 1854. Demostró la correlación entre las áreas residenciales en el mapa del centro de Londres cuyos residentes habían estado usando una bomba de agua específica y las áreas con más muertes debido al brote. ^[26]

Ingeniería

• En física de polímeros , los diagramas de Voronoi se pueden utilizar para representar volúmenes libres de polímeros.
• En la ciencia de los materiales , las microestructuras policristalinas en aleaciones metálicas se representan comúnmente mediante teselaciones de Voronoi.
• En el crecimiento de islas, se utiliza el diagrama de Voronoi para estimar la tasa de crecimiento de islas individuales. ^{[27] [28] [29] [30] [31]}
• En física del estado sólido , la celda de Wigner-Seitz es la teselación de Voronoi de un sólido, y la zona de Brillouin es la teselación de Voronoi del espacio recíproco ( número de onda ) de cristales que tienen la simetría de un grupo espacial.
• En aviación , los diagramas de Voronoi se superponen a los mapas de trazado oceánico para identificar el aeródromo más cercano para el desvío en vuelo (ver ETOPS ), a medida que una aeronave avanza en su plan de vuelo.
• En arquitectura , los patrones Voronoi fueron la base de la propuesta ganadora para la remodelación del Centro de Artes de Gold Coast . ^[32]
• En la planificación urbana , los diagramas de Voronoi se pueden utilizar para evaluar el sistema de zonas de carga de mercancías. ^[33]
• En minería , los polígonos de Voronoi se utilizan para estimar las reservas de materiales valiosos, minerales u otros recursos. Los pozos de exploración se utilizan como el conjunto de puntos en los polígonos de Voronoi.
• En metrología de superficies , la teselación de Voronoi se puede utilizar para modelar la rugosidad de la superficie . ^[34]
• En robótica , algunas de las estrategias de control y algoritmos de planificación de rutas ^[35] de sistemas multi-robot se basan en la partición de Voronoi del entorno. ^{[36] [37]}

Matemáticas

• Se puede construir una estructura de datos de ubicación de puntos sobre el diagrama de Voronoi para responder a consultas de vecino más cercano , donde se desea encontrar el objeto que está más cerca de un punto de consulta determinado. Las consultas de vecino más cercano tienen numerosas aplicaciones. Por ejemplo, se puede 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 , que se utiliza comúnmente 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 entre un conjunto de puntos y en un polígono circundante; por ejemplo, para construir un nuevo supermercado lo más lejos posible de todos los existentes, ubicado en una determinada ciudad.
• Los diagramas de Voronoi junto con los diagramas de Voronoi de punto más lejano se utilizan para algoritmos eficientes para calcular la redondez de un conjunto de puntos. ^[12] El enfoque de Voronoi también se utiliza en la evaluación de la circularidad/ redondez al evaluar el conjunto de datos de una máquina de medición de coordenadas .
• Los ceros de las derivadas iteradas de una función racional en el plano complejo se acumulan en los bordes del diagrama de Voronoi del conjunto de los polos (teorema de los condados de Pólya ^[38] ).

Informática

• En redes , los diagramas de Voronoi se pueden utilizar para derivar la capacidad de una red inalámbrica .
• En gráficos por computadora , los diagramas de Voronoi se utilizan para calcular patrones geométricos de fracturamiento/fragmentación en 3D. También se utilizan para generar de manera procedimental texturas orgánicas o con apariencia de lava.
• En la navegación autónoma de robots , se utilizan diagramas de Voronoi para encontrar rutas claras. Si los puntos son obstáculos, los bordes del gráfico serán las rutas más alejadas de los obstáculos (y, en teoría, de cualquier colisión).
• En el aprendizaje automático , los diagramas de Voronoi se utilizan para realizar clasificaciones 1-NN . ^[39]
• En la reconstrucción de escenas globales, incluso con sitios de sensores aleatorios y flujo de estela inestable, datos geofísicos y datos de turbulencia 3D, se utilizan teselaciones de Voronoi con aprendizaje profundo . ^[40]
• En el desarrollo de la interfaz de usuario , se pueden utilizar patrones de Voronoi para calcular el mejor estado de desplazamiento para un punto determinado. ^[41]

Educación cívica y planificación

• En Melbourne , los estudiantes de las escuelas públicas siempre tienen derecho a asistir a la escuela primaria o secundaria más cercana a su lugar de residencia, medida en línea recta. Por lo tanto, el mapa de zonas escolares es un diagrama de Voronoi. ^[42]

Panadería

• La pastelera ucraniana Dinara Kasko utiliza los principios matemáticos del diagrama de Voronoi para crear moldes de silicona hechos con una impresora 3D para dar forma a sus originales pasteles. ^[43]

Algoritmos

Se conocen varios algoritmos eficientes para construir diagramas de Voronoi, ya sea directamente (como el diagrama en sí) 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. El algoritmo de 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 Jump Flooding puede generar diagramas de Voronoi aproximados en tiempo constante y es adecuado para su uso en hardware gráfico de consumo. ^{[44] [45]}

El algoritmo de Lloyd y su generalización a través del algoritmo de Linde–Buzo–Gray (también conocido como agrupamiento de k-medias ) utilizan la construcción de diagramas de Voronoi como una 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 los puntos semilla se mueven a nuevas ubicaciones que son más centrales dentro de sus celdas. Estos métodos se pueden utilizar en espacios de dimensión arbitraria para converger iterativamente hacia una forma especializada del diagrama de Voronoi, llamada teselación de Voronoi centroidal , 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.

• 
  Puntos aleatorios en 3D para formar una partición Voronoi 3D
• 
  Malla Voronoi 3D de 25 puntos aleatorios
• 
  Malla Voronoi 3D de 25 puntos aleatorios con opacidad de 0,3 y puntos
• 
  Malla Voronoi 3D de 25 piezas de poliedros convexos de puntos aleatorios

Véase también

• Triangulación de Delaunay
• Segmentación de mapas
• Método de elementos naturales
• Interpolación de vecinos naturales
• Interpolación del vecino más próximo
• Diagrama de potencia
• Polo Voronoi

Notas

1. Burrough, Peter A.; McDonnell, Rachael; McDonnell, Rachael A.; Lloyd, Christopher D. (2015). "8.11 Vecinos más próximos: polígonos de Thiessen (Dirichlet/Voroni)". Principios de los sistemas de información geográfica . Oxford University Press. págs. 160–. ISBN 978-0-19-874284-5.
2. Longley, Paul A.; Goodchild, Michael F.; Maguire, David J.; Rhind, David W. (2005). "14.4.4.1 Polígonos de Thiessen". Sistemas de información geográfica y ciencia . Wiley. págs. 333–. ISBN 978-0-470-87001-3.
3. Sen, Zekai (2016). "2.8.1 Polígonos de Delaney, Varoni y Thiessen". Principios de modelado espacial en ciencias de la Tierra . Springer. págs. 57–. ISBN 978-3-319-41758-5.
4. Aurenhammer, Franz (1991). "Diagramas de Voronoi: un estudio de una estructura de datos geométrica fundamental". ACM Computing Surveys . 23 (3): 345–405. doi :10.1145/116873.116880. S2CID  4613674.
5. Okabe, Atsuyuki; Boots, Barry; Sugihara, Kokichi; Chiu, Sung Nok (2000). Teselaciones espaciales: conceptos y aplicaciones de los diagramas de Voronoi (2.ª ed.). John Wiley. ISBN 978-0-471-98635-5.
6. Boyd, Stephen; Vandenberghe, Lieven (2004). Optimización convexa . Ejercicio 2.9: Cambridge University Press. pág. 60.{{cite book}}: Mantenimiento de CS1: ubicación ( enlace )
7. Tran, QT; Tainar, D.; Safar, M. (2009). Transacciones sobre sistemas de datos y conocimiento a gran escala . Springer. pág. 357. ISBN. 9783642037214.
8. Reem 2009.
9. Reem 2011.
10. Senechal, Marjorie (21 de mayo de 1993). "Estructuras matemáticas: teselaciones espaciales. Conceptos y aplicaciones de los diagramas de Voronoi. Atsuyuki Okabe, Barry Boots y Kokichi Sugihara. Wiley, Nueva York, 1992. xii, 532 pp., illus. $89.95. Serie Wiley en probabilidad y estadística matemática". Science . 260 (5111): 1170–1173. doi :10.1126/science.260.5111.1170. ISSN  0036-8075. PMID  17806355.
11. Voronoï 1908a y Voronoï 1908b.
12. de Berg, Mark ; van Kreveld, Marc ; Overmars, Marcos ; Schwarzkopf, Otfried (2008). Geometría computacional (Tercera ed.). Springer-Verlag . ISBN 978-3-540-77974-2.7.4 Diagramas de Voronoi de punto más lejano. Incluye una descripción del algoritmo.
13. Skyum, Sven (18 de febrero de 1991). "Un algoritmo simple para calcular el círculo envolvente más pequeño". Information Processing Letters . 37 (3): 121–125. doi :10.1016/0020-0190(91)90030-L., contiene un algoritmo simple para calcular el diagrama de Voronoi del punto más lejano.
14. Biedl, Therese ; Grimm, Carsten; Palios, Leonidas; Shewchuk, Jonathan ; Verdonschot, Sander (2016). "Realización de diagramas de Voronoi de punto más lejano". Actas de la 28.ª Conferencia Canadiense sobre Geometría Computacional (CCCG 2016) .
15. Edelsbrunner, Herbert (2012) [1987]. "13.6 Diagramas de potencia". Algoritmos en geometría combinatoria . Monografías de la EATCS sobre informática teórica. Vol. 10. Springer-Verlag. págs. 327–328. ISBN 9783642615689.
16. Sunil Arya, Sunil; Malamatos, Theocharis; Mount, David M. (2002). "Diagramas de Voronoi aproximados con eficiencia espacial". Actas del trigésimo cuarto simposio anual de la ACM sobre teoría de la computación . págs. 721–730. doi :10.1145/509907.510011. ISBN. 1581134959.S2CID 1727373  .
17. Hölscher, Tonio; Krömker, Susanne; Mara, Hubert (2020). "Der Kopf Sabouroff en Berlín: Zwischen archäologischer Beobachtung und geometrischer Vermessung". Gedenkschrift für Georgios Despinis (en alemán). Atenas, Grecia: Museo Benaki .
18. Celdas de Voronoi y distancias geodésicas - Sabouroff head en YouTube . Análisis utilizando el marco de software GigaMesh como lo describen Hölscher et al. cf. doi:10.11588/heidok.00027985.
19. Laver, Michael; Sergenti, Ernest (2012). Competencia entre partidos: un modelo basado en agentes . Princeton: Princeton University Press. ISBN 978-0-691-13903-6.
20. Bock, Martin; Tyagi, Amit Kumar; Kreft, Jan-Ulrich; Alt, Wolfgang (2009). "Teselación de Voronoi generalizada como modelo de dinámica de tejido celular bidimensional". Boletín de biología matemática . 72 (7): 1696–1731. arXiv : 0901.4469v1 . Código Bibliográfico :2009arXiv0901.4469B. doi :10.1007/s11538-009-9498-3. PMID  20082148. S2CID  16074264.
21. Hui Li (2012). Baskurt, Atilla M; Sitnik, Robert (eds.). "Modelado espacial de la microarquitectura ósea". Procesamiento de imágenes tridimensionales (3Dip) y aplicaciones II . 8290 : 82900P. Código Bibliográfico : 2012SPIE.8290E..0PL. doi : 10.1117/12.907371. S2CID  1505014.
22. Sanchez-Gutierrez, D.; Tozluoglu, M.; Barry, JD; Pascual, A.; Mao, Y.; Escudero, LM (4 de enero de 2016). "Las limitaciones físicas celulares fundamentales impulsan la autoorganización de los tejidos". The EMBO Journal . 35 (1): 77–88. doi :10.15252/embj.201592374. PMC 4718000 . PMID  26598531. 
23. Feinstein, Joseph; Shi, Wentao; Ramanujam, J.; Brylinski, Michal (2021). "Bionoi: una representación basada en diagramas de Voronoi de sitios de unión de ligandos en proteínas para aplicaciones de aprendizaje automático". En Ballante, Flavio (ed.). Interacciones proteína-ligando y diseño de fármacos. Métodos en biología molecular. Vol. 2266. Nueva York, NY: Springer US. págs. 299–312. doi :10.1007/978-1-0716-1209-5_17. ISBN 978-1-0716-1209-5. PMID  33759134. S2CID  232338911. Consultado el 23 de abril de 2021 .
24. Springel, Volker (2010). "E pur si moove: simulaciones hidrodinámicas cosmológicas invariantes de Galileo en una malla móvil". MNRAS . 401 (2): 791–851. arXiv : 0901.4107 . Código Bibliográfico :2010MNRAS.401..791S. doi : 10.1111/j.1365-2966.2009.15715.x . S2CID  119241866.
25. Kasim, Muhammad Firmansyah (1 de enero de 2017). "Sombragrafía cuantitativa y radiografía de protones para modulaciones de gran intensidad". Physical Review E . 95 (2): 023306. arXiv : 1607.04179 . Bibcode :2017PhRvE..95b3306K. doi :10.1103/PhysRevE.95.023306. PMID  28297858. S2CID  13326345.
26. Steven Johnson (19 de octubre de 2006). El mapa fantasma: la historia de la epidemia más aterradora de Londres y cómo cambió la ciencia, las ciudades y el mundo moderno. Penguin Publishing Group. pág. 187. ISBN 978-1-101-15853-1. Recuperado el 16 de octubre de 2017 .
27. Mulheran, PA; Blackman, JA (1996). "Zonas de captura y escalamiento en el crecimiento homogéneo de películas delgadas". Physical Review B . 53 (15): 10261–7. Bibcode :1996PhRvB..5310261M. doi :10.1103/PhysRevB.53.10261. PMID  9982595.
28. Pimpinelli, Alberto; Tumbek, Levent; Winkler, Adolf (2014). "Igualdades de escala y exponentes en la nucleación de islas: nuevos resultados y aplicación a películas orgánicas". The Journal of Physical Chemistry Letters . 5 (6): 995–8. doi :10.1021/jz500282t. PMC 3962253 . PMID  24660052. 
29. Fanfoni, M.; Placidi, E.; Arciprete, F.; Orsini, E.; Patella, F.; Balzarotti, A. (2007). "Nucleación repentina versus invariancia de escala de puntos cuánticos de InAs en GaAs". Revisión física B. 75 (24): 245312. Código bibliográfico : 2007PhRvB..75x5312F. doi : 10.1103/PhysRevB.75.245312. ISSN  1098-0121. S2CID  120017577.
30. Miyamoto, Satoru; Moutanabbir, Oussama; Haller, Eugene E.; Itoh, Kohei M. (2009). "Correlación espacial de nanoislas de Ge/Si(001) isotópicamente puras autoensambladas". Physical Review B . 79 (165415): 165415. Bibcode :2009PhRvB..79p5415M. doi :10.1103/PhysRevB.79.165415. ISSN  1098-0121. S2CID  13719907.
31. Löbl, Matthias C.; Zhai, Liang; Jahn, Jan-Philipp; Ritzmann, Julian; Huo, Yongheng; Wieck, Andreas D.; Schmidt, Oliver G.; Ludwig, Arne; Rastelli, Armando; Warburton, Richard J. (3 de octubre de 2019). "Correlaciones entre las propiedades ópticas y el área de celdas de Voronoi de puntos cuánticos". Physical Review B . 100 (15): 155402. arXiv : 1902.10145 . Código Bibliográfico :2019PhRvB.100o5402L. doi :10.1103/physrevb.100.155402. ISSN  2469-9950. S2CID  119443529.
32. "RECINTO CULTURAL DE GOLD COAST". ARM Architecture. Archivado desde el original el 7 de julio de 2016. Consultado el 28 de abril de 2014 .
33. Lopez, C.; Zhao, C.-L.; Magniol, S; Chiabaut, N; Leclercq, L (28 de febrero de 2019). "Simulación microscópica de cruceros para estacionamiento de camiones como medida para gestionar la zona de carga de mercancías". Sustainability . 11 (5), 1276.
34. Singh, K.; Sadeghi, F.; Correns, M.; Blass, T. (diciembre de 2019). "Un enfoque basado en la microestructura para modelar los efectos de la rugosidad de la superficie en la fatiga por tracción". Revista internacional de fatiga . 129 : 105229. doi :10.1016/j.ijfatigue.2019.105229. S2CID  202213370.
35. Niu, Hanlin; Savvaris, Al; Tsourdos, Antonios; Ji, Ze (2019). "Algoritmo de planificación de rutas basado en mapas de carreteras con visibilidad de Voronoi para vehículos de superficie no tripulados" (PDF) . The Journal of Navigation . 72 (4): 850–874. doi :10.1017/S0373463318001005. S2CID  67908628.
36. Cortes, J.; Martínez, S.; Karatas, T.; Bullo, F. (abril de 2004). "Control de cobertura para redes de detección móviles". IEEE Transactions on Robotics and Automation . 20 (2): 243–255. doi :10.1109/TRA.2004.824698. ISSN  2374-958X. S2CID  2022860.
37. Teruel, Enrique; Aragues, Rosario; López-Nicolás, Gonzalo (abril de 2021). "Un método práctico para cubrir uniformemente una región dinámica con un enjambre". IEEE Robotics and Automation Letters . 6 (2): 1359–1366. doi :10.1109/LRA.2021.3057568. ISSN  2377-3766. S2CID  232071627.
38. Pólya, G. Sobre los ceros de las derivadas de una función y su carácter analítico. Boletín de la AMS, Volumen 49, Número 3, 178-191, 1943.
39. Mitchell, Tom M. (1997). Aprendizaje automático (edición internacional). McGraw-Hill. pág. 233. ISBN 978-0-07-042807-2.
40. Shenwai, Tanushree (18 de noviembre de 2021). "Una nueva técnica de aprendizaje profundo que reconstruye campos globales sin utilizar datos de sensores organizados". MarkTechPost . Consultado el 5 de diciembre de 2021 .
41. Archivado en Ghostarchive y Wayback Machine: «Mark DiMarco: Algoritmos de interfaz de usuario [JSConf2014]». 11 de junio de 2014 – vía www.youtube.com.
42. "Encuentra mi escuela". Departamento de Educación del Gobierno de Victoria . Consultado el 25 de julio de 2023 .
43. Haridy, Rich (6 de septiembre de 2017). "Arquitecto convertido en pastelero ofrece deliciosos pasteles geométricos impresos en 3D". New Atlas .
44. Rong, Guodong; Tan, Tiow Seng (2006). "Inundación de saltos en GPU con aplicaciones al diagrama de Voronoi y la transformada de distancia" (PDF) . En Olano, Marc; Séquin, Carlo H. (eds.). Actas del Simposio de 2006 sobre gráficos 3D interactivos, SI3D 2006, 14-17 de marzo de 2006, Redwood City, California, EE. UU. . ACM. págs. 109-116. doi :10.1145/1111411.1111431. ISBN. 1-59593-295-X.
45. "Juguete sombreado".

Referencias

• Aurenhammer, Franz ; Klein, Rolf; Lee, Der-Tsai (2013). Diagramas de Voronoi y triangulaciones de Delaunay . World Scientific. ISBN 978-9814447638.
• Bowyer, Adrian (1981). "Computación de teselaciones de Dirichlet". Comput. J. 24 (2): 162–166. doi : 10.1093/comjnl/24.2.162 .
• de Berg, Mark; van Kreveld, Marc; Overmars, Marcos ; Schwarzkopf, Otfried (2000). "7. Diagramas de Voronoi". Geometría computacional (2ª edición revisada). Saltador. págs. 47-163. ISBN 978-3-540-65620-3. Incluye una descripción del algoritmo de Fortune.
• Klein, Rolf (1988). "Diagramas de Voronoi abstractos y sus aplicaciones: resumen extendido". Geometría computacional y sus aplicaciones . Apuntes de clase en informática . Vol. 333. Springer. págs. 148–157. doi :10.1007/3-540-50335-8_31. ISBN . 978-3-540-52055-9.
• Lejeune Dirichlet, G. (1850). "Über die Reduktion der positivn quadratischen Formen mit drei unbestimmten ganzen Zahlen". Journal für die Reine und Angewandte Mathematik . 1850 (40): 209–227. doi :10.1515/crll.1850.40.209. S2CID  199546675.
• Okabe, Atsuyuki; Boots, Barry; Sugihara, Kokichi ; Chiu, Sung Nok (2000). Teselaciones espaciales: conceptos y aplicaciones de los diagramas de Voronoi (2.ª ed.). Wiley. ISBN 0-471-98635-6.
• Reem, Daniel (2009). "Un algoritmo para calcular diagramas de Voronoi de generadores generales en espacios normados generales". Actas del Sexto Simposio Internacional sobre Diagramas de Voronoi en Ciencia e Ingeniería (ISVD 2009) . pp. 144–152. doi :10.1109/ISVD.2009.23. ISBN 978-1-4244-4769-5.
• Reem, Daniel (2011). "La estabilidad geométrica de los diagramas de Voronoi con respecto a pequeños cambios de los sitios". Actas del vigésimo séptimo simposio anual sobre geometría computacional . pp. 254–263. arXiv : 1103.4125 . Bibcode :2011arXiv1103.4125R. doi :10.1145/1998196.1998234. ISBN 9781450306829.S2CID14639512  .​
• Thiessen, Alfred H. (julio de 1911). "Precipitaciones medias para grandes áreas". Monthly Weather Review . 39 (7). American Meteorological Society: 1082–1089. Bibcode :1911MWRv...39R1082T. doi : 10.1175/1520-0493(1911)39<1082b:pafla>2.0.co;2 .
• Voronoï, Georges (1908a). "Nuevas aplicaciones de parámetros continúa à la théorie des formes quadratiques. Premier mémoire. Sur quelques propriétés des formes quadratiques positivs parfaites" (PDF) . Journal für die Reine und Angewandte Mathematik . 1908 (133): 97-178. doi :10.1515/crll.1908.133.97. S2CID  116775758.
• Voronoï, Georges (1908b). "Nuevas aplicaciones de parámetros continúa à la théorie des formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs" (PDF) . Journal für die Reine und Angewandte Mathematik . 1908 (134): 198–287. doi :10.1515/crll.1908.134.198. S2CID  118441072.
• Watson, David F. (1981). "Cálculo de la teselación de Delaunay n-dimensional con aplicación a los politopos de Voronoi". Comput. J. 24 (2): 167–172. doi : 10.1093/comjnl/24.2.167 .

Enlaces externos

• 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 fuego de estepa