miniaturadeimagen|20 puntos en el plano y su partición del plano en regiones de Voronoi.
Los polígonos de Thiessen, nombrados en honor al meteorólogo estadounidense Alfred H. Thiessen, son una construcción geométrica que permite construir una partición del plano euclídeo. Estos objetos también fueron estudiados por el matemático ucraniano Gueorgui Voronói en 1907, de donde toman el nombre alternativo de diagramas de Voronoi o teselación de Voronoi, y por el matemático alemán Gustav Lejeune Dirichlet en 1850, de donde toman el nombre de teselación de Dirichlet.
Los diagramas de Voronoi son uno de los métodos de interpolación más simples, basados en la distancia euclidiana, especialmente apropiada cuando los datos son cualitativos. Se crean al unir los puntos entre sí, trazando las mediatrices de los segmentos de unión. Los segmentos determinados por las intersecciones de estas mediatrices determinan una serie de polígonos en un espacio bidimensional alrededor de un conjunto de puntos de control, de manera que el perímetro de los polígonos generados sea equidistante a los puntos vecinos y designen su área de influencia.
Diagramas de Voronói en el plano euclidiano ℝ2
La forma más fácil e intuitiva de visualizar a los diagramas de Voronói es a través de su representación en el plano euclídeo. En la literatura clásica se supone el hecho de contar con un conjunto de establecimientos que se desean colocar sobre una cierta región geográfica de tal manera que las ubicaciones sean lo más rentables posible. Por tanto, se debe hallar una configuración que permita que el número de clientes atraídos sea el más factible. La suposición lógica indica que los clientes irían al establecimiento más cercano a su domicilio y no a aquellos que sean muy lejanos. Con base en esto, los diagramas de Voronói otorgan la configuración deseada por los establecimientos. El diagrama de Voronói induce una subdivisión del plano euclidiano (la región geográfica) en función de un conjunto de sitios (los establecimientos), donde a cada sitio se le asocia una y solamente una subdivisión. Además, cada subdivisión engloba todos los puntos más cercanos al sitio asociado a los sitios restantes, a esto se lo denomina un modelo de asignamiento de Voronói.
Definición formal marco|100px|Los cuatro sitios más externos tiene asociados regiones de Voronói abiertas caracterizadas por las semi-aristas.
En primera instancia, denotemos a la distancia euclidiana entre dos puntos y por . En el plano entonces se tiene:
miniaturadeimagen|Construcción de la región de Voronói de un sitio debido a la intersección de semi-planos.
Sea el conjunto de puntos distintos en el plano que son denominados como sitios. Se define el diagrama de Voronói de como la subdivisión del plano en regiones, una para cada , cumpliendo la propiedad de proximidad en la que un punto pertenece a la región de un sitio si y sólo si para cada . Se denotará al diagrama de Voronói de mediante . Cada región que corresponde a un sitio se denotará como y será llamada región de Voronói de .
La región de Voronói para un sitio está construida a partir de las intersecciones de los semiplanos formados al trazar los bisectores de hacia los sitios . Tomando el caso donde únicamente hay dos sitios y , se traza el segmento de recta y posteriormente se traza el bisector de . Este bisector parte el plano en dos semiplanos, donde el semiplano que contiene a (representado como ) representa el lugar geométrico de todos los puntos más cercanos a que a ; y el semiplano que contiene a () alberga a todos los puntos más próximos a que a . De acuerdo con esto, entonces se puede establecer de forma general cómo se define la región de Voronói para un sitio .
está compuesta por la intersección de semiplanos que conforman una región poligonal convexa que puede ser abierta o cerrada. La región está acotada por un máximo de vértices y un máximo de aristas. Se tienen estas cantidades de vértices y aristas debido a que los sitios más lejanos suelen tener asociados regiones de Voronói no acotadas conformadas por aristas y semi-aristas (aristas que tienen un vértice de inicio pero no uno final).
Propiedades A continuación se enunciarán un conjunto de propiedades del Diagrama de Voronói donde se asume que no puede haber cuatro puntos del conjunto original en posición cocircular. En caso de que esta situación no sea contemplada, entonces se deben considerar una gran cantidad de detalles que deben ser agregados a las diferentes propiedades.
Teorema 1. Sea un conjunto de sitios en el plano. Si todos los sitios son colineales, entonces consiste de líneas paralelas. De otra forma, es conexo y sus aristas podrían ser segmentos o semi-líneas. Teorema 2. Para , el número de vértices en el diagrama de Voronói de un conjunto de sitios en el plano es a lo más y el número de aristas es a lo más .
La siguiente propiedad ayuda a caracterizar los vértices y aristas que componen el diagrama de Voronói. Sin embargo, es necesario definir qué significa el círculo vacío más grande de , denotado como . Para un punto , se define como el círculo más grande que tiene a como su centro y no contiene ningún otro sitio de en su interior. Teorema 3. Para un diagrama de Voronói de un conjunto de sitios lo siguiente se cumple: Un punto es un vértice de si y solo si su más grande círculo vacío contiene tres o más sitios en su contorno. El bisector entre los sitios y define una arista de si y solo si hay un punto sobre el bisector tal que contiene tanto a y a en su contorno pero no otro sitio. Teorema 4. Cada vecino más cercano del sitio en define una arista de . Teorema 5. La región de Voronói es abierta si y solo si es un punto en la envolvente convexa del conjunto . Teorema 6. La gráfica dual del diagrama de Voronói define la triangulación de Delaunay.
Algoritmos para la construcción del Diagrama de Voronói Algoritmo por fuerza bruta Una primera aproximación para la construcción del diagrama de Voronói consiste en explotar la geometría de cada región de Voronói. Por cada sitio se construirá su región de Voronói mediante el cálculo explícito de los semiplanos originados debido a los bisectores trazados con respecto a los demás sitios. Posteriormente, se computará la intersección de estos semiplanos para, finalmente, dar origen a .
Este algoritmo tiene muchas desventajas de entre las cuales se tienen las que a continuación se describen. En primera instancia, el cálculo explícito de los semi-planos y su intersección puede provocar problemas de precisión en la computadora generado, evidentemente, una versión incorrecta de . El segundo inconveniente involucra que no se produce información inmediata y que se pueda aprovechar acerca del vecindario de cada sitio. Finalmente, dado que se trata del algoritmo de un algoritmo ineficiente, no resulta extraño descubrir que su complejidad computacional sea alta. El algoritmo está en el orden de Algoritmo divide y vencerás Este algoritmo está fundamentado sobre el paradigma de diseño de algoritmos divide y vencerás. Dado el problema de construir el diagrama de Voronói para el conjunto de sitios, ahora se dividirá a este último en dos subconjuntos y , con aproximadamente el mismo tamaño, de los que se debe encontrar su diagrama de Voronoi independientemente. Finalmente, y deben ser unidos para poder obtener . Sin embargo, ¿qué razón existe para que se crea que y tengan alguna relación con ?
Para que se pueda contestar la última pregunta, es necesario definir construcciones geométricas que serán de vital importancia.
Definición 1. Dado una petición de , sea el conjunto de aristas de Voronoi que son compartidas por pares de regiones de Voronoi y .
La colección de aristas tiene las siguientes propiedades.
Teorema 7 es el conjunto de aristas de una subgráfica de con las siguientes propiedades: consta de ciclos y cadenas de aristas disjuntas. Si una cadena tiene una sola arista, ésta es una línea recta; de otra forma sus dos aristas extremas son rayos seminfinitos. Si y son linealmente separados (si más de un punto pertenece a la línea de separación, todos estos puntos son asignados a un mismo conjunto de la partición), entonces consiste de una sola cadena monotónica.
Con el fin de separar a en dos subconjuntos se le deberá ordenar con respecto a las abcisas y tomar la recta que pase por la mediana, de tal suerte que se tengan dos subconjuntos de aproximadamente el mismo tamaño. Adicionalmente, dada esta elección de recta de separación, se puede decir que parte al plano en una porción izquierda y una porción derecha . Con base en esto, se tiene la siguiente propiedad:
Teorema 8. Si y son linealmente separados por una línea vertical con a la izquierda y a la derecha, entonces el diagrama de Voronoi es la unión de y .
A partir del último teorema es que se puede responder la pregunta inicial acerca de cómo se vinculan dos diagramas de Voronoi de dos particiones para generar el diagrama de Voronoi de todo el conjunto de sitios. El siguiente algoritmo establece la forma de calcular el diagrama de Voronoi mediante la técnica divide y vencerás.
Procedimiento DIAGRAMA DE VORONOI Paso 1. Partir a en dos subconjunto y , de aproximadamente el mismo tamaño, mediante la mediana en las coordenadas x.
Paso 2. Construir y recursivamente.
Paso 3. Construir la cadena polígona , separando a y .
Paso 4. Descartar todas las aristas de que estén a la izquierda de . El resultado es , el diagrama de Voronoi del diagrama entero.
Algoritmo de Fortune (barrido de recta)
Inspiración
El algoritmo de fuerza bruta previamente revisado tiene una complejidad , sin embargo, debido al teorema 2, se puede suponer que hay una forma mucho más eficiente de encontrar el diagrama de Voronoi pues sus elementos constituyentes tienen complejidad . En efecto, existe este algoritmo y es llamado Algoritmo de FortuneSteven Fortune. A sweepline algorithm for Voronoi diagrams. Proceedings of the second annual symposium on Computational geometry. Yorktown Heights, New York, United States, pp.313–322. 1986. ISBN 0-89791-194-6. ACM Digital LibrarySpringerLink en honor a Steven Fortune quien lo inventó en 1986 y cuya complejidad es .
miniaturadeimagen|derecha|Cálculo del diagrama de Voronoi con ayuda de la técnica de barrido de recta. Se nota que conforme la recta se mueve, la línea de playa cambia generando las regiones de Voronoi de los sitios.
El algoritmo de Fortune está basado en una de las técnicas clave dentro de la geometría computacional denominada barrido de recta. La esencia de esta técnica yace en suponer que existe una recta que recorre el plano de arriba hacia abajo (o de izquierda a derecha, incluso en direcciones opuestas) y que a lo largo de su recorrido se interseca con las estructuras que deseamos procesar. Cuando se da esta intersección, se guarda cierta información de tal forma que ayude en los cálculos. Es necesario que la información que se haya obtenido en regiones ya visitadas por la recta sea invariante. Es muy común que está técnica utilice dos tipos de estructuras de datos: cola de prioridades donde se guardan eventos que no son más que puntos donde la recta debe detenerse y un árbol binario de búsqueda donde se almacenan los elementos geométricos que se han intersecado con la recta y se necesita recordar para el procesamiento futuro. Cabe resaltar que debido a que en la computadora no se puede emular tal cual el movimiento continuo de la recta de barrido, se requiere idear una forma de discretización del movimiento de la recta que sea procesable en la computadora, de ahí que los eventos sean tal discretización.
Propiedades combinatorias