Diagrama de Voronoi

El diagrama de Voronoi de un conjunto finito de puntos S en un plano representa tal partición del plano, en la que cada área de esta partición forma un conjunto de puntos que están más cerca de uno de los elementos del conjunto S que de cualquier otro elemento del conjunto [1] .

Nombrado en honor a Georgy Feodosevich Voronoi , quien estudió el caso general n -dimensional en 1908 [2] . También conocido como: Mosaico de Voronoi, Mosaico de Voronoi, Mosaico de Dirichlet .

Historia

Por primera vez, el uso de tales estructuras se atribuye a Descartes en 1644. Dirichlet usó diagramas de Voronoi bidimensionales y tridimensionales en su trabajo sobre formas cuadráticas en 1850.

Propiedades

Tiene una estrecha conexión y correspondencia biunívoca con la triangulación de Delaunay . Es decir, si conectamos puntos con aristas cuyas regiones de Voronoi lindan entre sí, el gráfico resultante será una triangulación de Delaunay.

Algoritmos de construcción

Un algoritmo simple

Considere la bisectriz perpendicular de un segmento que conecta un par de puntos y . $pags$ $q$

Esta perpendicular divide el plano en dos semiplanos y , y el área de Voronoi del punto p está contenida enteramente en uno de ellos, y el área del punto está contenida en el otro. La región del punto de Voronoi coincide con la intersección de todos estos semiplanos : $H_{{pq}}$ $H_{{qp}}$ $q$ $V_{p}$ $pags$ $H_{{pq}}$

$V_{p}=\bigcap \limits _{q\in S/\{p\}}H_{pq}$ .

Así, la solución del problema se reduce al cálculo de dicha intersección para cada punto . El algoritmo se puede implementar con complejidad computacional [3] . $pags$ $O(n^{4})$

Algoritmo de la fortuna

El algoritmo se basa en el uso de una línea de barrido. La línea de barrido es un objeto auxiliar que representa una línea recta vertical. En cada paso del algoritmo, se construye un diagrama de Voronoi para un conjunto que consta de una línea de barrido y puntos a su izquierda. En este caso, el límite entre el área de Voronoi, la línea y las áreas de puntos consiste en segmentos de parábolas (ya que el lugar geométrico de los puntos equidista de un punto dado y la línea es una parábola ). La línea recta se mueve de izquierda a derecha. Cada vez que pasa por otro punto, este punto se suma a la sección ya construida del diagrama. Agregar un punto a un diagrama utilizando un árbol de búsqueda binaria tiene una complejidad de , puntos totales , y la clasificación de puntos por coordenadas se puede realizar en , por lo que la complejidad computacional del algoritmo de Fortune es . $O(\log n)$ $norte$ $X$ $O(n\log n)$ $O(n\log n)$

Algoritmo recursivo

La idea principal del algoritmo recursivo es utilizar el método de programación dinámica . El conjunto inicial de puntos se divide en dos subconjuntos y se construye un diagrama de Voronoi para cada uno de ellos, y luego los diagramas resultantes se combinan en uno. La partición del conjunto se realiza mediante una recta que divide el plano en dos semiplanos, de manera que ambos semiplanos contengan aproximadamente el mismo número de puntos. La unión de diagramas de conjuntos y de Voronoi se puede realizar en el tiempo , por lo que la complejidad computacional del algoritmo es . $S$ $S_{1}$ $S_{2}$ $S$ $S_{1}$ $S_{2}$ $En)$ $O(n\log n)$

Generalizaciones

Un diagrama de Voronoi se puede definir de manera obvia para un conjunto de puntos en un espacio euclidiano arbitrario , no necesariamente bidimensional. Se cumple la siguiente afirmación: en el espacio -dimensional, el número de simples de la triangulación de Delaunay -dimensional de un conjunto de puntos puede alcanzar . Por lo tanto, los costos de memoria requeridos para almacenar el diagrama dual de Voronoi son del mismo orden. $k$ $k$ $norte$ $O(n^{{\lceil {\frac k2}\rceil }})$

Se puede definir un diagrama de Voronoi para un espacio con una métrica no euclidiana . Sin embargo, en este caso, los límites entre las regiones de Voronoi adyacentes pueden no ser variedades de primer orden (por ejemplo, cuando se usa la distancia de Manhattan ).

El conjunto S puede consistir no solo en puntos, sino también en cualquier objeto para el cual se determina la distancia a un punto arbitrario del plano. En este caso, los elementos del conjunto S se denominan sitios. Un ejemplo es el diagrama de polígono de Voronoi , donde los sitios son los vértices y los bordes del polígono. Dichos diagramas se utilizan para construir ejes medianos y se utilizan ampliamente en problemas de análisis de imágenes. El límite de las regiones del diagrama del polígono de Voronoi es la unión de segmentos de línea y parábolas.

Aplicación

La partición de Voronoi se utiliza en la ciencia de materiales computacionales para crear agregados policristalinos sintéticos. También se utiliza en gráficos por computadora para subdividir superficies aleatoriamente.

El método de Gold (o "método de robo de área") es un método de interpolación de una función en 2D, utilizado, por ejemplo, en geodesia. Se construye un diagrama de Voronoi de todos los puntos, después de lo cual se le agrega el punto deseado. La nueva celda "selecciona" el área de las existentes; cuanta más área se tome prestada de ( x i , y i , z i ), mayor será el coeficiente en ese punto.

Además, la partición de Voronoi se usa para encontrar la estimación superior del número cromático para el espacio euclidiano ( el problema de Nelson-Erdős-Hadwiger ) de dimensión 2 o 3. Aquí, la partición del plano en polígonos de Voronoi para una red dada es consideró. Se encontró la mejor estimación para espacios bidimensionales y tridimensionales al considerar una partición simétrica. Por ejemplo, teselar un plano con hexágonos (en este caso, un hexágono es un polígono de Voronoi).

Véase también

Enlaces

Algoritmo de Fortune Archivado el 13 de junio de 2008 en Wayback Machine .
Visualizador de algoritmos de fortuna

Fuentes

↑ F. Preparata, M. Sheimos. Geometría computacional: una introducción. Copia de archivo fechada el 23 de abril de 2011 en Wayback Machine - M.: Mir, 1989. Págs. 295
↑ GF Voronoi. Nouvelles application des paramètres continus à la théorie de formesatiques (francés) // Journal für die reine und angewandte Mathematik. - 1908. - Vol. 134 . - pág. 198-287 .
↑ Diagrama de Voronoi . MAXimal (26 de enero de 2009). Consultado el 8 de junio de 2021. Archivado desde el original el 8 de junio de 2021. (Ruso)