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 con su triangulación de Delaunay .
El diagrama de Voronoi es el nombre de Gueorgui Voronói , y también se llama una teselación de Voronoi , una descomposición de Voronoi , una partición de Voronoi , o una teselación de Dirichlet (después de Peter Gustav Lejeune Dirichlet ). Las células de Voronoi también se conocen como polígonos de Thiessen . [1] [2] [3] Los diagramas de Voronoi tienen aplicaciones prácticas y teóricas en muchos campos, principalmente en la ciencia y la tecnología , pero también en las artes visuales . [4] [5]
El caso mas simple
En el caso más simple, que se muestra en la primera imagen, se nos da un conjunto finito de puntos { p 1 , ..., p n } en el plano euclidiano . En este caso, cada sitio p k es simplemente un punto, y su celda de Voronoi correspondiente 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 estas celdas se obtiene de la intersección de medios espacios y, por lo tanto, es un poliedro (convexo) . [6] Los segmentos de línea del diagrama de Voronoi son todos los puntos en el plano que son equidistantes a los dos sitios más cercanos. Los vértices ( nodos ) de Voronoi son los puntos equidistantes a tres (o más) sitios.
Definicion formal
Dejar ser un espacio métrico con función de distancia. Dejar ser un conjunto de índices y dejar ser una tupla (colección ordenada) de subconjuntos no vacíos (los sitios) en el espacio. La celda de Voronoi, o región de Voronoi,, asociado con el sitio es el conjunto de todos los puntos en cuya distancia a no es mayor que su distancia a los otros sitios , dónde es cualquier índice diferente de . En otras palabras, si denota la distancia entre el punto y el subconjunto , luego
El diagrama de Voronoi es simplemente la tupla de células. 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 generalmente se supone que no están unidos. 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.
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 células de Voronoi son politopos convexos y se pueden representar de manera 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 celdas de Voronoi pueden no ser convexas o 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 con un punto generador . Dejarser el conjunto de todos los puntos en el espacio euclidiano. Dejar ser un punto que genera su región de Voronoi , que genera , y que genera , y así. 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".
Ilustración
Como ilustración simple, considere un grupo de tiendas en una ciudad. Suponga que queremos estimar el número de clientes de una tienda determinada. Siendo todo lo demás 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 más cercana a 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 esta tienda (que está modelada por un punto en nuestra ciudad).
Para la mayoría de las ciudades, la distancia entre puntos se puede medir usando la distancia euclidiana familiar :
o la distancia de Manhattan :
- .
Los diagramas de Voronoi correspondientes se ven diferentes para diferentes métricas de distancia.
Propiedades
- El gráfico dual para 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.
- Suponga que el escenario es el plano euclidiano y se da un grupo de puntos diferentes. Entonces, dos puntos son adyacentes en el casco convexo 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 se puede representar como una unión de segmentos lineales 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 posiblemente un espacio uniformemente convexo de dimensión infinita , puede haber un número infinito de sitios de una 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, p. Ej. , 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 investigacion
El uso informal de los diagramas de Voronoi se remonta a Descartes en 1644. Peter Gustav Lejeune Dirichlet utilizó diagramas de Voronoi bidimensionales y tridimensionales en su estudio de las formas cuadráticas en 1850. El médico británico John Snow utilizó un diagrama similar a Voronoi en 1854 para ilustre 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 de Broad Street infectada que de cualquier otra bomba de agua.
Los diagramas de Voronoi llevan el nombre de Georgy Feodosievych Voronoy, quien definió y estudió el caso n- dimensional general en 1908. [10] Los diagramas de Voronoi que se utilizan en geofísica y meteorología para analizar datos distribuidos espacialmente (como las mediciones de lluvia) se denominan polígonos de Thiessen después de American el meteorólogo 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, teselación (es) de Voronoi, teselación (es) de Dirichlet.
Ejemplos de
Los mosaicos de Voronoi de celosías regulares de puntos en dos o tres dimensiones dan lugar a muchos mosaicos familiares.
- Una celosía 2D da una teselación de panal irregular, con hexágonos iguales con simetría de puntos; en el caso de una celosía triangular regular, es regular; en el caso de una celosía rectangular, los hexágonos se reducen a rectángulos en filas y columnas; una celosía cuadrada da la teselación regular de cuadrados; tenga en cuenta que los rectángulos y los cuadrados también pueden ser generados por otras celosías (por ejemplo, la celosía definida por los vectores (1,0) y (1 / 2,1 / 2) da cuadrados).
- Una celosía cúbica simple da el panal cúbico .
- Una celosía hexagonal compacta da una teselación del espacio con dodecaedros trapezo-rómbicos .
- Una celosía cúbica centrada en las caras da una teselación del espacio con dodecaedros rómbicos .
- Una celosía 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 celosías 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 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 de forma recursiva. Para generar el diagrama de Voronoi de n- ésimo orden a partir del conjunto S , comience con el diagrama de orden ( n - 1) ésimo y reemplace cada celda generada por X = { x 1 , x 2 , ..., x n −1 } con un diagrama Voronoi generado en el conjunto de S - X .
Diagrama de Voronoi del punto más lejano
Para un conjunto de n puntos, el diagrama de Voronoi de orden ( n - 1) -ésimo se denomina diagrama de Voronoi del punto más lejano.
Para un conjunto dado de puntos S = { p 1 , p 2 , ..., 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 Voronoi más lejano punto si y sólo si es un vértice del casco convexo de P . Sea H = { h 1 , h 2 , ..., h k } el casco convexo 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 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 . [11] [12]
Los límites de las células en el diagrama de Voronoi del punto más lejano tienen la estructura de un árbol topológico , con infinitos rayos como hojas. Cada árbol finito es isomorfo al árbol formado de esta manera a partir de un diagrama de Voronoi del punto más lejano. [13]
Generalizaciones y variaciones
Como implica la definición, las celdas de Voronoi se pueden definir 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 células de Voronoi pueden ser más complicados que en el caso euclidiano, ya que el lugar geométrico equidistante para dos puntos puede no ser el subespacio de codimensión 1, incluso en el caso bidimensional.
Un diagrama de Voronoi ponderado es aquel en el que la función de un par de puntos para definir una celda de Voronoi es una función de distancia modificada por pesos multiplicativos o aditivos asignados a puntos generadores. En contraste con el caso de las celdas de Voronoi definidas usando 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. [14]
El diagrama de Voronoi de puntos en -el espacio dimensional puede tener vértices, que requieren el mismo límite para la cantidad de memoria necesaria para almacenar una descripción explícita de la misma. Por lo tanto, los diagramas de Voronoi a menudo no son factibles para dimensiones moderadas o altas. Una alternativa más eficiente en cuanto al espacio es utilizar diagramas de Voronoi aproximados . [15]
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), esqueleto recto y diagramas de zona . Además de los puntos, estos diagramas utilizan líneas y polígonos como semillas. Al aumentar el diagrama con segmentos de línea que se conectan a los puntos más cercanos de las semillas, se obtiene una subdivisión plana del entorno. [16] Esta estructura se puede utilizar como una malla de navegación para buscar caminos a través de grandes espacios. La malla de navegación se ha generalizado para admitir entornos 3D de varias capas, como un aeropuerto o un edificio de varias plantas. [17]
Aplicaciones
Humanidades
- 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 el tipo de estatua a la que puede haber pertenecido una cabeza cortada. Un ejemplo de esto que hizo uso de las celdas de Voronoi fue la identificación de la cabeza de Sabouroff , que hizo uso de una malla poligonal de alta resolución . [18] [19]
Ciencias Naturales
- 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 un área, basándose en una serie de mediciones puntuales. En este uso, generalmente se les conoce como 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 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 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 adaptativas en las imágenes, agregando flujos de señal en cada una. El principal objetivo 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 puede usarse para definir los dominios computacionales usados 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 , los modelos de tejido muscular, basados en diagramas de Voronoi, se pueden utilizar para detectar enfermedades neuromusculares. [22]
- En epidemiología , los diagramas de Voronoi se pueden utilizar para correlacionar las fuentes de infección 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]
Ingenieria
- 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 usando teselaciones de Voronoi. En el crecimiento de islas, el diagrama de Voronoi se utiliza para estimar la tasa de crecimiento de islas individuales. [27] [28] [29] [30] En la 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 en cartas de trazado oceánico para identificar el aeródromo más cercano para la desviación en vuelo (ver ETOPS ), a medida que una aeronave avanza a través de su plan de vuelo.
- En arquitectura , los patrones de Voronoi fueron la base de la obra ganadora para la remodelación del Arts Center Gold Coast . [31]
- En la planificación urbana , los diagramas de Voronoi se pueden utilizar para evaluar el sistema de zona de carga de mercancías. [32]
- En minería , los polígonos de Voronoi se utilizan para estimar las reservas de materiales valiosos, minerales u otros recursos. Las perforaciones exploratorias 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 el modelado de rugosidad de superficies . [33]
- En robótica , algunas de las estrategias de control de los sistemas de múltiples robots se basan en la partición del entorno de Voronoi. [34] [35]
Geometría
- Se puede construir una estructura de datos de ubicación de puntos sobre el diagrama de Voronoi para responder las consultas de los vecinos más cercanos , donde se desea encontrar el objeto más cercano a un punto de consulta determinado. Las consultas de vecinos más cercanos 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 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 para que los algoritmos eficientes calculen la redondez de un conjunto de puntos. [11] El enfoque de Voronoi también se utiliza en la evaluación de circularidad / redondez mientras se evalúa el conjunto de datos de una máquina de medición de coordenadas .
Informática
- En redes , los diagramas de Voronoi se pueden utilizar en derivaciones de 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 de forma procedimental texturas orgánicas o con aspecto 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, 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 hacer clasificaciones 1-NN . [36]
- En el desarrollo de la interfaz de usuario , los patrones de Voronoi se pueden utilizar para calcular el mejor estado de desplazamiento para un punto determinado. [37]
Educación cívica y planificación
- En Melbourne , los estudiantes de las escuelas públicas siempre son elegibles para asistir a la escuela primaria o secundaria más cercana a su lugar de residencia, medido por una distancia en línea recta. El mapa de zonas escolares es, por tanto, un diagrama de Voronoi. [38]
Panadería
- La chef 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 pasteles originales.
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 de O ( n log ( n )) a O ( n 2 ) 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 básico. [39] [40]
El algoritmo de Lloyd y su generalización a través del algoritmo 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 Centroidal de Voronoi , donde los sitios se han movido a puntos que también son los centros geométricos de sus celdas.
Ver también
- Triangulación de Delaunay
- Segmentación de mapas
- Método de elementos naturales
- Interpolación de vecino natural
- Interpolación del vecino más cercano
- Diagrama de potencia
- Poste de Voronoi
Notas
- ^ Burrough, Peter A .; McDonnell, Rachael; 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.
- ^ 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.
- ^ 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.
- ^ Aurenhammer, Franz (1991). "Diagramas de Voronoi - un estudio de una estructura de datos geométrica fundamental". Encuestas de computación ACM . 23 (3): 345–405. doi : 10.1145 / 116873.116880 . S2CID 4613674 .
- ^ Okabe, Atsuyuki; Botas, 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.
- ^ Boyd, Stephen; Vandenberghe, Lieven (2004). Optimización convexa . Ejercicio 2.9: Cambridge University Press. pag. 60.Mantenimiento de CS1: ubicación ( enlace )
- ^ Tran, QT; Tainar, D .; Safar, M. (2009). Transacciones en sistemas centrados en datos y conocimiento a gran escala . pag. 357. ISBN 9783642037214.
- ^ Reem 2009 .
- ^ Reem 2011 .
- ^ Voronoï 1908a y Voronoï 1908b .
- ^ a b de Berg, Mark ; van Kreveld, Marc ; Overmars, Mark ; 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.
- ^ Skyum, Sven (18 de febrero de 1991). "Un algoritmo simple para calcular el círculo envolvente 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.
- ^ Biedl, Therese ; Grimm, Carsten; Palios, Leonidas; Shewchuk, Jonathan ; Verdonschot, Sander (2016). "Realización de diagramas de Voronoi del punto más lejano". Actas de la 28a Conferencia Canadiense de Geometría Computacional (CCCG 2016) .
- ^ Edelsbrunner, Herbert (2012) [1987]. "13.6 Diagramas de potencia". Algoritmos en geometría combinatoria . EATCS Monografías sobre Informática Teórica. 10 . Springer-Verlag. págs. 327–328. ISBN 9783642615689..
- ^ Sunil Arya, Sunil; Malamatos, Theocharis; Monte, David M. (2002). "Diagramas de Voronoi aproximados de espacio eficiente". Actas del trigésimo cuarto simposio anual de ACM sobre teoría de la computación . págs. 721–730. doi : 10.1145 / 509907.510011 . ISBN 1581134959. S2CID 1727373 .
- ^ Geraerts, Roland (2010), Planning Short Paths with Clearance using Explicit Corridors (PDF) , Conferencia internacional sobre robótica y automatización, IEEE, págs. 1997–2004.
- ^ van Toll, Wouter G .; Cook IV, Atlas F .; van Kreveld, Marc J .; Geraerts, Roland (2018), El eje medial de un entorno multicapa y su aplicación como malla de navegación (PDF) , Transacciones ACM en sistemas y algoritmos espaciales, págs. 2: 1–2: 34, arXiv : 1701.05141.
- ^ 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
- ^ Células de Voronoi y distancias geodésicas: cabeza de Sabouroff en YouTube . Análisis utilizando el marco de software GigaMesh como lo describen Hölscher et al. cf. doi: 10.11588 / heidok.00027985 .
- ^ 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 .
- ^ 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 .
- ^ a b 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" . El diario EMBO . 35 (1): 77–88. doi : 10.15252 / embj.201592374 . PMC 4718000 . PMID 26598531 .
- ^ Feinstein, Joseph; Shi, Wentao; Ramanujam, J .; Brylinski, Michal (2021), Ballante, Flavio (ed.), "Bionoi: A Voronoi Diagram-Based Representation of Ligand-Binding Sites in Proteins for Machine Learning Applications" , Interacciones proteína-ligando y diseño de fármacos , Métodos en biología molecular, Nueva York, NY: Springer US, 2266 , págs. 299–312, doi : 10.1007 / 978-1-0716-1209-5_17 , ISBN 978-1-0716-1209-5, PMID 33759134 , consultado el 23 de abril de 2021
- ^ Springel, Volker (2010). "E pur si muove: 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 .
- ^ Kasim, Muhammad Firmansyah (1 de enero de 2017). "Shadowgraphy cuantitativo y radiografía de protones para modulaciones de gran intensidad". Revisión E física . 95 (2): 023306. arXiv : 1607.04179 . Código bibliográfico : 2017PhRvE..95b3306K . doi : 10.1103 / PhysRevE.95.023306 . PMID 28297858 . S2CID 13326345 .
- ^ 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 .
- ^ Mulheran, PA; Blackman, JA (1996). "Captura de zonas y descamación en crecimiento homogéneo de película fina". Physical Review B . 53 (15): 10261–7. Código bibliográfico : 1996PhRvB..5310261M . doi : 10.1103 / PhysRevB.53.10261 . PMID 9982595 .
- ^ Pimpinelli, Alberto; Tumbek, Levent; Winkler, Adolf (2014). "Igualdad de escala y exponente en la nucleación de islas: resultados novedosos y aplicación a películas orgánicas" . La Revista de Cartas de Química Física . 5 (6): 995–8. doi : 10.1021 / jz500282t . PMC 3962253 . PMID 24660052 .
- ^ 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". Physical Review B . 75 (24): 245312. Código Bibliográfico : 2007PhRvB..75x5312F . doi : 10.1103 / PhysRevB.75.245312 . ISSN 1098-0121 .
- ^ 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. Código Bibliográfico : 2009PhRvB..79p5415M . doi : 10.1103 / PhysRevB.79.165415 . ISSN 1098-0121 . S2CID 13719907 .
- ^ "PRECINTO CULTURAL DE LA COSTA DE ORO" . Arquitectura ARM.
- ^ López, C .; Zhao, C.-L .; Magniol, S; Chiabaut, N; Leclercq, L (28 de febrero de 2019). “Simulación Microscópica de Cruising para Estacionamiento de Camiones como Medida para Manejo de Zona de Cargamento de Mercancías” . Sustentabilidad . 11 (5), 1276.
- ^ 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 .
- ^ Cortes, J .; Martinez, S .; Karatas, T .; Bullo, F. (abril de 2004). "Control de cobertura para redes de sensores 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 .
- ^ 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 .
- ^ Mitchell, Tom M. (1997). Aprendizaje automático (edición internacional). McGraw-Hill. pag. 233 . ISBN 978-0-07-042807-2.
- ^ "Algoritmos de interfaz de usuario" .
- ^ "Zonas escolares" . Departamento de Educación y Capacitación del Gobierno de Victoria . Consultado el 24 de agosto de 2020 .
- ^ https://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf
- ^ "Shadertoy" .
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 teselados de Dirichlet" . Computación. J. 24 (2): 162–166. doi : 10.1093 / comjnl / 24.2.162 .
- de Berg, Mark; van Kreveld, Marc; Overmars, Mark ; Schwarzkopf, Otfried (2000). "7. Diagramas de Voronoi" . Geometría computacional (2ª ed. Revisada). Saltador. págs. 47-163. ISBN 978-3-540-65620-3. Incluye una descripción del algoritmo de Fortune.
- Klein, Rolf (1989). "Diagramas abstractos de Voronoi y sus aplicaciones". Geometría computacional y sus aplicaciones . Apuntes de conferencias en informática . 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 Positiven 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 .
- Okabe, Atsuyuki; Botas, 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 normativos 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 .
- Reem, Daniel (2011). "La estabilidad geométrica de los diagramas de Voronoi con respecto a pequeños cambios de los sitios". Actas del 27º Simposio anual de ACM sobre geometría computacional (SoCG) : 254–263. arXiv : 1103.4125 . Código Bibliográfico : 2011arXiv1103.4125R . doi : 10.1145 / 1998196.1998234 . ISBN 9781450306829. S2CID 14639512 .
- Voronoï, Georges (1908a). "Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Premier mémoire. Sur quelques propriétés des formes quadratiques positives 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). "Nouvelles applications des paramètres continus à 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" . Computación. J. 24 (2): 167-172. doi : 10.1093 / comjnl / 24.2.167 .
enlaces externos
- Diagramas de Voronoi y Delaunay interactivos en tiempo real con código fuente
- Demostración de varias métricas
- Mathworld en diagramas de Voronoi
- Diagramas de Voronoi: aplicaciones desde la arqueología hasta la zoología
- Diagramas de Voronoi en CGAL , la biblioteca de algoritmos de geometría computacional
- Más discusiones y galería de imágenes sobre teselaciones centroidales de Voronoi
- Diagramas de Voronoi por Ed Pegg, Jr. , Jeff Bryant y Theodore Gray , Wolfram Demonstrations Project .
- Un diagrama de Voronoi en una esfera, en 3d y otros
- Trazar un diagrama de Voronoi con Mathematica
- Teselado de Voronoi: teselado de Voronoi interactivo con D3.js
- Diagrama de Voronoi interactivo y visualización de interpolación de vecinos naturales (WebGL)
Software
Los diagramas de Voronoi requieren un paso de cálculo antes de mostrar los resultados. Por lo tanto, una herramienta eficiente procesaría el cálculo en tiempo real para mostrar un resultado directo al usuario. Existen muchas aplicaciones comerciales y gratuitas. Un tipo de herramientas particularmente prácticas son las basadas en la web. Las herramientas basadas en la web son más fáciles de acceder y consultar. Además, al ser SVG un formato soportado de forma nativa por la web, permite al mismo tiempo un renderizado eficiente (acelerado por GPU) y es un formato estándar soportado por múltiples herramientas CAD (por ejemplo, Autodesk Fusion360).
- Voronator es una herramienta gratuita (basada en anuncios) que actúa sobre mallas de objetos 3D para aplicar Voronoi en su superficie. Aunque la herramienta actúa en 3d, el procesamiento de voronoi se basa en su superficie 2d.
- rhill voronoi es una biblioteca JavaScript de código abierto para la generación 2d voronoi.
- stg voronoi es un proyecto de github con una aplicación web simple que ofrece una visualización interactiva de las celdas de voronoi al mover el mouse. También proporciona una exportación SVG.
- websvg voronoi es una aplicación web receptiva para la edición y exportación de voronoi en SVG. También permite exportar e importar las coordenadas de las semillas. Está basado en 2d y se diferencia de las herramientas mencionadas anteriormente por proporcionar una operación de retracción de celdas, que no se basa en la escala, sino en la traslación de los bordes. Un borde puede eliminarse si es consumido por sus bordes vecinos.
- R.Beutel voronoi utiliza WebGL y proporciona, además de la visualización estática, un movimiento animado de las células voronoi.
Aunque voronoi es un concepto muy antiguo, las herramientas disponibles actualmente carecen de múltiples funciones matemáticas que podrían agregar valores a estos programas. [ opinión ] Los ejemplos podrían ser el uso de una distancia de costo diferente a la euclidiana, y principalmente algoritmos voronoi 3d. Aunque no son herramientas de software en sí mismas, la primera referencia explica el concepto de voronoi 3d y la segunda es una biblioteca de voronoi 3d.
- Diagramas de Voronoi 3D y eje medial
- Voro ++ Una biblioteca de c ++ para el cálculo de voronoi 3d