Diagramas De Voronoi

Diagramas de Voronoi

En matemáticas, un diagrama de Voronoi es una manera de dividir el espacio en un número de regiones. Un conjunto de puntos (llamados semillas, sitios, o generadores) se especifica de antemano y para cada semilla habrá una región correspondiente que consta de todos los puntos más cercanos a la semilla que a cualquier otro. Las regiones se llaman celdas de Voronoi. Es dualpara la triangulación de Delaunay.
Lleva el nombre de Georgy Voronoi, y también se llama una teselación de Voronoi, una descomposición de Voronoi, o un mosaico de Dirichlet (después de Lejeune Dirichlet). Diagramas de Voronoi se pueden encontrar en un gran número de campos de la ciencia y la tecnología, incluso en el arte, y se han encontrado numerosas aplicaciones prácticas y teóricas.
El casomás sencillo
En el caso más simple y más familiar (que se muestra en la primera imagen), se nos da un conjunto finito de puntos {p1, ..., pn} en el plano euclidiano. En este caso, cada pk sitio es simplemente un punto y su celda de Voronoi correspondiente (también llamada región de Voronoi o célula Dirichlet) Rk que consiste en todos los puntos cuya distancia a pk es menor que o igual a sudistancia a cualquier otro sitio. Cada célula tal se obtiene de la intersección de la media-espacios, y por lo tanto es un polígono convexo. Los segmentos del diagrama Voronoi son todos los puntos en el plano que son equidistantes de los dos sitios más cercanos. Los vértices de Voronoi (nodos) son los puntos equidistantes a tres (o más) sitios.
Definición formal

El diagrama de Voronoi es simplementela tupla de células. En principio algunos de los sitios puede intersectar e incluso coinciden, pero por lo general se supone que son disjuntos. Además, los sitios infinitos están permitidos en la definición, pero una vez más, en muchos casos, sólo un número finito de sitios son considerados.
En el caso particular en que el espacio es un espacio euclidiano dimensional finito, cada sitio es unpunto, hay un número finito de puntos y todos ellos son diferentes, entonces las celdas de Voronoi son politopos convexos y pueden ser representados de una manera combinatoria utilizando su vértices, lados, 2-dimensional caras, etc A veces, la estructura combinatoria inducido se hace referencia como el diagrama de Voronoi. Sin embargo, en general, las celdas de Voronoi no puede ser convexa o inclusoconectado.
Ilustración
Como un ejemplo simple, considere un grupo de tiendas en una ciudad plana. Supongamos que queremos estimar el número de clientes de una tienda determinada. Con todo lo demás constante (precio, producto, calidad de servicio, etc), es razonable asumir que los clientes elegir su tienda preferida simplemente por consideraciones distancia: van a ir a la tienda situada más próximaa ellos. En este caso, la celda de Voronoi de una determinada tienda puede ser utilizado para dar una estimación aproximada del número de clientes potenciales que van a esta tienda (que es modelado por un punto en nuestra ciudad plana).
Hasta ahora se ha supuesto que la distancia entre puntos en la ciudad se miden utilizando la distancia estándar, es decir, la distancia euclídeana familiar:Sin embargo, si consideramos el caso donde los clientes sólo ir a las tiendas de un vehículo y las rutas de tráfico son paralelos a los ejes y  , como en Manhattan, a continuación, una función de distancia más realista será la distancia  , llamada  .

10 tiendas en una ciudad plana y sus celdas Voronoi (distancia euclidiana). Las mismas 10 tiendas, actualmenteen la distancia de Manhattan. Esto muestra que las celdas de Voronoi depende significativamente de la métrica utilizada.

Propiedades
*

* El gráfico dual para un diagrama de Voronoi (en el caso de un espacio euclídeo con sitios puntuales) corresponde a la triangulación de Delaunay para el mismo conjunto de puntos.
* El par más cercano de puntos corresponde a dos células...