diagrama de voronói

Tipo de partición plana

20 puntos y sus células 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 un conjunto determinado de objetos. Se puede clasificar también como 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 existe una región correspondiente , llamada célula de Voronoi , formada por 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 le llama 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 células 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 la ciencia y la tecnología , pero también en las 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 correspondiente celda de Voronoi consta de cada punto en el plano euclidiano para el cual es el sitio más cercano: la distancia a es menor o igual a la distancia mínima a cualquier otro sitio . Para otro sitio , los puntos que están más cerca que , 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 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 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}$

Definicion formal

Sea un espacio métrico con función de distancia . Sea un conjunto de índices y 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 cualquier índice es 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 cruzarse e incluso coincidir (a continuación se describe una aplicación para sitios que representan tiendas), pero normalmente se supone que son disjuntos. Además, se permiten una cantidad infinita de 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 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 de forma combinatoria usando sus vértices, lados, caras bidimensionales, etc. A veces, la estructura combinatoria inducida se denomina diagrama de Voronoi. Sin embargo, en general, las células de Voronoi pueden no ser convexas ni siquiera estar conectadas.

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 del espacio euclidiano. Sea un punto que genera su región de Voronoi , que genera , y que genera , y así sucesivamente. Entonces, 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". ${\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

Como ejemplo sencillo, consideremos un grupo de tiendas en una ciudad. Supongamos que queremos estimar el número de clientes de una tienda determinada. En igualdad de condiciones (precio, productos, calidad del servicio, etc.), es razonable suponer que los clientes eligen su tienda preferida simplemente por consideraciones de distancia: acudirán a la tienda situada más cerca de ellos. En este caso, la celda 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 está modelada por un punto en 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

• La gráfica 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 se da un conjunto discreto de puntos. Entonces dos puntos del conjunto son adyacentes en la cáscara convexa si y sólo 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 necesariamente se cumple cuando no se alcanza la distancia.
• En condiciones relativamente generales (el espacio es posiblemente un espacio uniformemente convexo de dimensión infinita , puede haber infinitos sitios de forma general, etc.) las células 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 traducción o distorsión, produce un pequeño cambio en la forma de las células de Voronoi. Ésta 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 a 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. ^[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 . quienes los usaron para estimar las precipitaciones a partir de mediciones dispersas en 1911. Otros nombres equivalentes para este concepto (o casos particularmente importantes del mismo): poliedros de Voronoi, polígonos de Voronoi, dominio(s) de influencia, descomposición de Voronoi, teselación(es) de Voronoi, Dirichlet teselación(es).

Ejemplos

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.

Los teselados de Voronoi de redes regulares de puntos en dos o tres dimensiones dan lugar a muchos teselados familiares.

• Una celosía 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 celosía cuadrada da el mosaico regular de cuadrados; tenga en cuenta 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 el panal cúbico .
• Una celosía hexagonal compacta da una teselación del espacio con dodecaedros trapezorómbicos .
• Una red cúbica centrada en las caras proporciona un mosaico del espacio con dodecaedros rómbicos .
• Una red cúbica centrada en el cuerpo da una teselación del espacio con octaedros truncados .
• Los planos paralelos con celosías triangulares regulares alineadas con los centros de cada uno dan el panal prismático hexagonal .
• Ciertas redes tetragonales centradas en el cuerpo dan una teselación del espacio con dodecaedros rombo-hexagonales .

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 solo punto en S , una celda de Voronoi de orden n 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 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 orden (} n  − 1 ) 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 sólo si es un vértice de la cáscara convexa de P. Sea H  = { h ₁ ,  h ₂ , ...,  h _k } la cáscara convexa de P ; entonces el diagrama de Voronoi del 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 sólo 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 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. ^[14]

Generalizaciones y variaciones.

Como lo 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 células de Voronoi pueden ser más complicados que en el caso euclidiano, ya que el lugar 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 células 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 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. ^[15]

El diagrama de Voronoi de puntos en un espacio de dimensiones 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. ^[dieciséis] ${\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 ingeniería hidrológica para encontrar los pesos de los datos de precipitación de las estaciones en un área (cuenca). Los puntos que generan los polígonos son las distintas estaciones que registran los datos de precipitación. Se dibujan bisectrices perpendiculares 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 media 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 arqueología clásica , específicamente en historia del arte , se analiza la simetría de las cabezas de las estatuas para determinar el tipo de estatua a la que pudo haber pertenecido una cabeza cortada. Un ejemplo de esto que hizo uso de células 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 los puntos del 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 emerge por crecimiento radial desde las semillas hacia afuera.

• En biología , los diagramas de Voronoi se utilizan para modelar varias 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 limitaciones 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 precipitación de una zona, a partir de una serie de mediciones puntuales. En este uso, generalmente se les denomina 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 bosques, 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 del rebaño 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 (p. ej., para clasificar las bolsas de unión en proteínas). ^[23] En otras aplicaciones, las células de Voronoi definidas por las posiciones de los núcleos en una molécula se utilizan para calcular las 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ñales 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 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 1854 en Broad Street en Soho, Inglaterra. Mostró 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 ciencia de materiales , las microestructuras policristalinas en aleaciones metálicas se representan comúnmente mediante teselaciones de Voronoi. En el crecimiento de las islas, el diagrama de Voronoi se utiliza 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 las cartas oceánicas 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 para la propuesta ganadora para la remodelación del Arts Center Gold Coast . ^[32]
• En 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, minerales u otros recursos valiosos. Las perforaciones exploratorias se utilizan como 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 multirobot se basan en la partición Voronoi del entorno. ^{[36] [37]}

Geometría

• Se puede construir una estructura de datos de ubicación de puntos sobre el diagrama de Voronoi para responder consultas del vecino más cercano , donde se desea encontrar el objeto más cercano a un punto de consulta determinado. Las consultas de vecino más cercano tienen numerosas aplicaciones. Por ejemplo, es posible que deseemos encontrar el hospital más cercano o el objeto más similar en una base de datos . Una aplicación importante 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 entre un conjunto de puntos y en un polígono circundante; por ejemplo, construir un nuevo supermercado lo más lejos posible de todos los existentes, en una ciudad determinada.
• Los diagramas de Voronoi junto con los diagramas de Voronoi del punto más lejano se utilizan como 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 circularidad/ redondez mientras se evalúa el conjunto de datos desde una máquina de medición de coordenadas .

informatica

• 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 rotura/fractura en 3D. También se utiliza para generar procedimentalmente texturas orgánicas o con apariencia de lava.
• En la navegación de robots autónomos , los diagramas de 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, en teoría, de cualquier colisión).
• En el aprendizaje automático , los diagramas de Voronoi se utilizan para realizar clasificaciones 1-NN . ^[38]
• 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, las teselaciones de Voronoi se utilizan con aprendizaje profundo . ^[39]
• En el desarrollo de interfaces de usuario , los patrones de Voronoi se pueden utilizar para calcular el mejor estado de desplazamiento para un punto determinado. ^[40]

Cívica y planificación

• En Melbourne , los estudiantes de escuelas públicas siempre son elegibles para asistir a la escuela primaria o secundaria más cercana a donde viven, medida por una distancia en línea recta. El mapa de zonas escolares es, por tanto, un diagrama de Voronoi. ^[41]

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. ^[42]

Algoritmos

Se conocen varios algoritmos eficientes para construir diagramas de Voronoi, ya sea directamente (como el diagrama mismo) 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 de gráficos básico. ^{[43] [44]}

El algoritmo de Lloyd y su generalización a través del algoritmo Linde-Buzo-Gray (también conocido como agrupación de k-medias ), 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 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 centroidal de Voronoi , donde los sitios se han movido a puntos que también son los centros geométricos de sus celdas.

Voronói 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 0,3 de opacidad y puntos
• 
  Malla Voronoi 3D de piezas de poliedros convexos de 25 puntos aleatorios

Ver 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 cercano
• Diagrama de potencia
• polo voronói

Notas

1. Burroughs, Peter A.; McDonnell, Raquel; McDonnell, Rachael A.; Lloyd, Christopher D. (2015). "8.11 Vecinos más cercanos: polígonos de Thiessen (Dirichlet/Voroni)". Principios de los Sistemas de Información Geográfica . Prensa de la Universidad de Oxford. págs.160–. ISBN 978-0-19-874284-5.
2. Longley, Paul A.; Goodchild, Michael F.; Maguire, David J.; Rind, 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 . Saltador. págs.57–. ISBN 978-3-319-41758-5.
4. Aurenhammer, Franz (1991). "Diagramas de Voronoi: un estudio de una estructura de datos geométricos fundamentales". Encuestas de Computación ACM . 23 (3): 345–405. doi :10.1145/116873.116880. S2CID  4613674.
5. Okabe, Atsuyuki; Botas, Barry; Sugihara, Kokichi; Chiu, Sung Nok (2000). Teselados espaciales: conceptos y aplicaciones de los diagramas de Voronoi (2ª ed.). Juan Wiley. ISBN 978-0-471-98635-5.
6. Boyd, Esteban; Vandenberghe, Lieven (2004). Optimizacion convexa . Ejercicio 2.9: Cambridge University Press. pag. 60.{{cite book}}: Mantenimiento CS1: ubicación ( enlace )
7. Tran, QT; Tainar, D.; Safar, M. (2009). Transacciones en sistemas centrados en datos y conocimiento a gran escala . Saltador. pag. 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 diagramas de Voronoi. Atsuyuki Okabe, Barry Boots y Kokichi Sugihara. Wiley, Nueva York, 1992. xii, 532 págs., ilus. $ 89,95. Serie Wiley en probabilidad y estadística matemática". Ciencia . 260 (5111): 1170-1173. doi : 10.1126/ciencia.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 del 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 circundante más pequeño". Cartas de procesamiento de información . 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, Teresa ; Grimm, Carsten; Palio, Leónidas; Shewchuk, Jonathan ; Verdonschot, Sander (2016). "Realización de diagramas de Voronoi del 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; Monte, David M. (2002). "Diagramas de Voronoi aproximados con eficiencia espacial". Actas del trigésimo cuarto simposio anual de ACM sobre teoría de la informática . 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. Células de Voronoi y distancias geodésicas: cabeza de Sabouroff en YouTube . Análisis utilizando el marco de software GigaMesh descrito por Hölscher et al. cf. doi:10.11588/heidok.00027985.
19. Laver, Michael; Sergenti, Ernesto (2012). Competencia partidista: un modelo basado en agentes . Princeton: Prensa de la Universidad de Princeton. ISBN 978-0-691-13903-6.
20. Bock, Martín; 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 Bib : 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 Bib : 2012SPIE.8290E..0PL. doi : 10.1117/12.907371. S2CID  1505014.
22. Sánchez-Gutiérrez, 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". La Revista EMBO . 35 (1): 77–88. doi :10.15252/embj.201592374. PMC 4718000 . PMID  26598531. 
23. Feinstein, José; 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, Nueva York: Springer EE. UU. 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 muove: simulaciones hidrodinámicas cosmológicas invariantes galileanas en una malla en movimiento". MNRAS . 401 (2): 791–851. arXiv : 0901.4107 . Código Bib : 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". Revisión física E. 95 (2): 023306. arXiv : 1607.04179 . Código bibliográfico : 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. Grupo Editorial Penguin. pag. 187.ISBN _ 978-1-101-15853-1. Consultado el 16 de octubre de 2017 .
27. Mulheran, Pensilvania; Blackman, JA (1996). "Capturar zonas y escalar en crecimiento homogéneo de películas delgadas". Revisión física B. 53 (15): 10261–7. Código bibliográfico : 1996PhRvB..5310261M. doi : 10.1103/PhysRevB.53.10261. PMID  9982595.
28. Pimpinelli, Alberto; Tumbek, Levent; Winkler, Adolf (2014). "Escala e igualdad de exponentes en la nucleación de islas: resultados novedosos y aplicación a películas orgánicas". La Revista de Letras de Química Física . 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". Revisión física B. 79 (165415): 165415. Código bibliográfico : 2009PhRvB..79p5415M. doi : 10.1103/PhysRevB.79.165415. ISSN  1098-0121. S2CID  13719907.
31. Löbl, Matías C.; Zhai, Liang; Jahn, Jan-Philipp; Ritzmann, Julián; Huo, Yongheng; Wieck, Andreas D.; Schmidt, Oliver G.; Luis, Arne; Rastelli, Armando; Warburton, Richard J. (3 de octubre de 2019). "Correlaciones entre las propiedades ópticas y el área de puntos cuánticos de la célula de Voronoi". Revisión física B. 100 (15): 155402. arXiv : 1902.10145 . Código Bib : 2019PhRvB.100o5402L. doi : 10.1103/physrevb.100.155402. ISSN  2469-9950. S2CID  119443529.
32. "RECINTO CULTURAL COSTA ORO". Arquitectura ARM. Archivado desde el original el 7 de julio de 2016 . Consultado el 28 de abril de 2014 .
33. López, C.; Zhao, CL; Magniol, S; Chiabaut, N; Leclercq, L (28 de febrero de 2019). "Simulación microscópica de crucero para estacionamiento de camiones como medida para la gestión de la zona de carga de mercancías". Sostenibilidad . 11 (5), 1276.
34. Singh, K.; Sadeghi, F.; Correns, M.; Blass, T. (diciembre de 2019). "Un enfoque basado en microestructura para modelar los efectos de la rugosidad de la superficie sobre 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 hojas de ruta de visibilidad de Voronoi para vehículos de superficie no tripulados" (PDF) . El Diario de Navegación . 72 (4): 850–874. doi :10.1017/S0373463318001005. S2CID  67908628.
36. Cortés, J.; Martínez, S.; Karatas, T.; Bullo, F. (abril de 2004). "Control de cobertura de redes de detección móviles". Transacciones IEEE sobre robótica y automatización . 20 (2): 243–255. doi :10.1109/TRA.2004.824698. ISSN  2374-958X. S2CID  2022860.
37. Teruel, Enrique; Aragües, Rosario; López-Nicolás, Gonzalo (abril 2021). "Un método práctico para cubrir uniformemente una región dinámica con un enjambre". Cartas de robótica y automatización IEEE . 6 (2): 1359-1366. doi :10.1109/LRA.2021.3057568. ISSN  2377-3766. S2CID  232071627.
38. Mitchell, Tom M. (1997). Aprendizaje automático (edición internacional). McGraw-Hill. pag. 233.ISBN _ 978-0-07-042807-2.
39. Shenwai, Tanushree (18 de noviembre de 2021). "Una novedosa técnica de aprendizaje profundo que reconstruye campos globales sin utilizar datos de sensores organizados". MarkTechPost . Consultado el 5 de diciembre de 2021 .
40. Archivado en Ghostarchive y Wayback Machine: "Mark DiMarco: Algoritmos de interfaz de usuario [JSConf2014]" - a través de www.youtube.com.
41. "Encuentra mi escuela". Departamento de Educación del Gobierno de Victoria . Consultado el 25 de julio de 2023 .
42. Haridy, rico (6 de septiembre de 2017). "El arquitecto convertido en pastelero sirve deliciosos pasteles geométricos impresos en 3D". Nuevo Atlas .
43. Rong, Guodong; Bronceado, Tiow Seng (2006). "Saltar la inundación en GPU con aplicaciones al diagrama de Voronoi y transformación de distancia" (PDF) . En Olano, Marc; Séquin, Carlo H. (eds.). Actas del Simposio de 2006 sobre gráficos 3D interactivos, SI3D 2006, 14 al 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.
44. "Juguete de sombras".

Referencias

• Aurenhammer, Franz ; Klein, Rolf; Lee, Der-Tsai (2013). Diagramas de Voronoi y Triangulaciones de Delaunay . Científico mundial. ISBN 978-9814447638.
• Bowyer, Adrián (1981). "Computación de teselados de Dirichlet". Computadora. 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 abstractos de voronoi y sus aplicaciones: resumen ampliado". Geometría Computacional y sus Aplicaciones . Apuntes de conferencias sobre informática . vol. 333. Saltador. 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; Botas, Barry; Sugihara, Kokichi ; Chiu, Sung Nok (2000). Teselados 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) . págs. 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 . págs. 254–263. arXiv : 1103.4125 . Código Bib : 2011arXiv1103.4125R. doi :10.1145/1998196.1998234. ISBN 9781450306829. S2CID  14639512.
• Thiessen, Alfred H. (julio de 1911). "Promedios de precipitaciones para grandes superficies". Revisión meteorológica mensual . Sociedad Meteorológica Estadounidense. 39 (7): 1082–1089. Código Bib : 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 politopos de Voronoi". Computadora. 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 estepario