Polígonos de Thiessen

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 segmento de unión. 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 designan su área de influencia.

Diagramas de Voronói en el plano euclidiano ${\displaystyle \mathbb {R} ^{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.[1]​

Definición formal

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 ${\displaystyle p}$ y ${\displaystyle q}$ por ${\displaystyle \|p-q\|}$. En el plano entonces se tiene:

${\displaystyle \|p-q\|={\sqrt {(p_{x}-q_{x})^{2}+(p_{y}-q_{y})^{2}}}}$

Construcción de la región de Voronói de un sitio debido a la intersección de semi-planos.

Sea ${\displaystyle P={p_{1},p_{2},\dots ,p_{n}}}$ el conjunto de ${\displaystyle n}$ puntos distintos en el plano que son denominados como sitios. Se define el diagrama de Voronói de ${\displaystyle P}$ como la subdivisión del plano en ${\displaystyle n}$ regiones, una para cada ${\displaystyle p_{i}\in P}$, cumpliendo la propiedad de proximidad en la que un punto ${\displaystyle q}$ pertenece a la región de un sitio ${\displaystyle p_{i}}$ si y sólo si ${\displaystyle \|q-p_{i}\|<\|q-p_{j}\|}$ para cada ${\displaystyle p_{j}\in P,j\neq i}$. Se denotará al diagrama de Voronói de ${\displaystyle P}$ mediante ${\displaystyle Vor(P)}$. Cada región que corresponde a un sitio ${\displaystyle p_{i}}$ se denotará como ${\displaystyle {\mathcal {V}}(p_{i})}$ y será llamada región de Voronói de ${\displaystyle p_{i}}$.

La región de Voronói para un sitio ${\displaystyle p_{i}}$ está construida a partir de las intersecciones de los semiplanos formados al trazar los bisectores de ${\displaystyle p_{i}}$ hacia los sitios ${\displaystyle p_{j},j\neq i}$. Tomando el caso donde únicamente hay dos sitios ${\displaystyle p}$ y ${\displaystyle q}$, se traza el segmento de recta ${\displaystyle {\overline {pq}}}$ y posteriormente se traza el bisector de ${\displaystyle {\overline {pq}}}$. Este bisector parte el plano en dos semiplanos, donde el semiplano que contiene a ${\displaystyle p}$ (representado como ${\displaystyle h(p,q)}$) representa el lugar geométrico de todos los puntos más cercanos a ${\displaystyle p}$ que a ${\displaystyle q}$; y el semiplano que contiene a ${\displaystyle q}$ (${\displaystyle h(q,p)}$) alberga a todos los puntos más próximos a ${\displaystyle q}$ que a ${\displaystyle p}$. De acuerdo con esto, entonces se puede establecer de forma general cómo se define la región de Voronói para un sitio ${\displaystyle p_{i}}$.

${\displaystyle {\mathcal {V}}(p_{i})=\bigcap _{j=1,j\neq i}^{n}h(p_{i},p_{j})}$

${\displaystyle {\mathcal {V}}(p_{i})}$ está compuesta por la intersección de ${\displaystyle n-1}$ semiplanos que conforman una región poligonal convexa que puede ser abierta o cerrada. La región está acotada por un máximo de ${\displaystyle n-1}$ vértices y un máximo de ${\displaystyle n-1}$ 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[1]​[2]​ del Diagrama de Voronói donde se asume que no puede haber cuatro puntos del conjunto original ${\displaystyle P}$ 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 ${\displaystyle P}$ un conjunto de ${\displaystyle n}$ sitios en el plano. Si todos los sitios son colineales, entonces ${\displaystyle Vor(P)}$ consiste de ${\displaystyle n-1}$ líneas paralelas. De otra forma, ${\displaystyle Vor(p)}$ es conexo y sus aristas podrían ser segmentos o semi-líneas.
• Teorema 2. Para ${\displaystyle n\geq 3}$, el número de vértices en el diagrama de Voronói de un conjunto de ${\displaystyle n}$sitios en el plano es a lo más ${\displaystyle 2n-5}$ y el número de aristas es a lo más ${\displaystyle 3n-6}$.

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 ${\displaystyle q}$, denotado como ${\displaystyle C_{P}(q)}$. Para un punto ${\displaystyle q}$, ${\displaystyle C_{P}(q)}$ se define como el círculo más grande que tiene a ${\displaystyle q}$ como su centro y no contiene ningún otro sitio de ${\displaystyle P}$ en su interior.

• Teorema 3. Para un diagrama de Voronói ${\displaystyle Vor(P)}$ de un conjunto de sitios ${\displaystyle P}$ lo siguiente se cumple:
  • Un punto ${\displaystyle q}$ es un vértice de ${\displaystyle Vor(P)}$ si y solo si su más grande círculo vacío ${\displaystyle C_{p}(q)}$ contiene tres o más sitios en su contorno.
  • El bisector entre los sitios ${\displaystyle p_{i}}$ y ${\displaystyle p_{j}}$ define una arista de ${\displaystyle Vor(P)}$ si y solo si hay un punto ${\displaystyle q}$ sobre el bisector tal que ${\displaystyle C_{p}(q)}$ contiene tanto a ${\displaystyle p_{i}}$ y a ${\displaystyle p_{j}}$ en su contorno pero no otro sitio.
• Teorema 4. Cada vecino más cercano del sitio ${\displaystyle p_{i}}$ en ${\displaystyle P}$ define una arista de ${\displaystyle {\mathcal {V}}(p_{i})}$.
• Teorema 5. La región de Voronói ${\displaystyle {\mathcal {V}}(p_{i})}$ es abierta si y solo si ${\displaystyle p_{i}}$ es un punto en la envolvente convexa del conjunto ${\displaystyle P}$.
• 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 ${\displaystyle p_{i}\in P}$ se construirá su región de Voronói mediante el cálculo explícito de los ${\displaystyle n-1}$ semiplanos originados debido a los bisectores trazados con respecto a los demás sitios. Posteriormente, se computará la intersección de estos ${\displaystyle n-1}$ semiplanos para, finalmente, dar origen a ${\displaystyle {\mathcal {V}}(p_{i})}$.

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 ${\displaystyle Vor(P)}$. 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 ${\displaystyle O(n^{2}\log {n})}$

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 ${\displaystyle P}$ de sitios, ahora se dividirá a este último en dos subconjuntos ${\displaystyle P_{1}}$ y ${\displaystyle P_{2}}$, con aproximadamente el mismo tamaño, de los que se debe encontrar su diagrama de Voronoi independientemente. Finalmente, ${\displaystyle Vor(P_{1})}$ y ${\displaystyle Vor(P_{2})}$ deben ser unidos para poder obtener ${\displaystyle Vor(P)}$. Sin embargo, ¿qué razón existe para que se crea que ${\displaystyle Vor(P_{1})}$ y ${\displaystyle Vor(P_{2})}$ tengan alguna relación con ${\displaystyle Vor(P)}$?

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 ${\displaystyle {P_{1}P_{2}}}$ de ${\displaystyle P}$, sea ${\displaystyle \sigma (P_{1},P_{2})}$ el conjunto de aristas de Voronoi que son compartidas por pares de regiones de Voronoi ${\displaystyle {\mathcal {V}}(p_{i}\in P_{1})}$ y ${\displaystyle {\mathcal {V}}(p_{j}\in P_{2})}$.

La colección de aristas ${\displaystyle \sigma (P_{1},P_{2})}$ tiene las siguientes propiedades.

Teorema 7 ${\displaystyle \sigma (P_{1},P_{2})}$es el conjunto de aristas de una subgráfica de ${\displaystyle Vor(P)}$ con las siguientes propiedades:

• ${\displaystyle \sigma (P_{1},P_{2})}$ 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 semi-infiitos.
• Si ${\displaystyle P_{1}}$ y ${\displaystyle P_{2}}$ 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 ${\displaystyle \sigma (P_{1},P_{2})}$ consiste de una sola cadena monotónica.

Con el fin de separar a ${\displaystyle P}$ en dos subconjuntos se le deberá ordenar con respecto a las abcisas y tomar la recta ${\displaystyle m}$ 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 ${\displaystyle \sigma }$ parte al plano en una porción izquierda ${\displaystyle \pi _{L}}$ y una porción derecha ${\displaystyle \pi _{R}}$. Con base en esto, se tiene la siguiente propiedad:

Teorema 8. Si ${\displaystyle P_{1}}$ y ${\displaystyle P_{2}}$ son linealmente separados por una línea vertical con ${\displaystyle P_{1}}$ a la izquierda y ${\displaystyle P_{2}}$ a la derecha, entonces el diagrama de Voronoi ${\displaystyle Vor(P)}$ es la unión de ${\displaystyle Vor(P_{1})\cap \pi _{L}}$ y ${\displaystyle Vor(P_{2})\cap \pi _{R}}$.

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[2]​ 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 ${\displaystyle P}$ en dos subconjunto ${\displaystyle P_{1}}$ y ${\displaystyle P_{2}}$, de aproximadamente el mismo tamaño, mediante la mediana en las coordenadas x.

Paso 2. Construir ${\displaystyle Vor(P_{1})}$ y ${\displaystyle Vor(P_{2})}$ recursivamente.

Paso 3. Construir la cadena polígona ${\displaystyle \sigma }$, separando a ${\displaystyle P_{1}}$ y ${\displaystyle P_{2}}$.

Paso 4. Descartar todas las aristas de ${\displaystyle Vor(P_{2})}$ que estén a la izquierda de ${\displaystyle \sigma }$. El resultado es ${\displaystyle Vor(P)}$, 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 ${\displaystyle O(n^{2}\log {n})}$ , 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 ${\displaystyle O(n)}$.[1]​ En efecto, existe este algoritmo y es llamado Algoritmo de Fortune[3]​ en honor a Steven Fortune quien lo inventó en 1986 y cuya complejidad es ${\displaystyle O(n\log {n})}$.[1]​

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 ${\displaystyle \ell }$ 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

Para aplicar el barrido de recta al diagrama de Voronoi, intuitivamente, se podría tomar al conjunto de sitios ${\displaystyle P={p_{1},\dots ,p_{n}}}$ como los eventos y de esta manera llevar la intersección de la recta de barrido con el diagrama de Voronoi. No obstante, debido a que el cálculo de ${\displaystyle {\mathcal {V}}(p_{i})}$ depende de la intersección de ${\displaystyle n-1}$ planos, entonces no se podría mantener el invariante de la técnica ya que aun cuando ${\displaystyle \ell }$ ya haya procesado un sitio, la información con respecto a su región de Voronoi seguirá cambiando debido a los sitios restantes por procesar. Con base en esto, es imperativo cambiar la perspectiva y en lugar de mantener la intersección de ${\displaystyle \ell }$ con ${\displaystyle Vor(P)}$ se necesita mantener la información acerca de aquellos sitios sobre ${\displaystyle \ell }$ que ya no podrá cambiar debido a los sitios debajo de ${\displaystyle \ell }$.

Línea de playa para el diagrama de Voronoi.

Se denotará al semi-plano cerrado sobre ${\displaystyle \ell }$ como ${\displaystyle \ell ^{+}}$. Se busca cuál es la parte del diagrama de Voronoi sobre ${\displaystyle \ell }$ que ya no podrá cambiar jamás, para lo cual se tiene lo siguiente. Dado un punto ${\displaystyle q\in \ell ^{+}}$, la distancia de éste a cualquier punto debajo de ${\displaystyle \ell }$ es más grande que la distancia de ${\displaystyle q}$ a ${\displaystyle \ell }$ propiamente. Además, el sitio más cercano ${\displaystyle q}$ no puede estar debajo de ${\displaystyle \ell }$ si ${\displaystyle q}$ es al menos tan cercano a algún sitio ${\displaystyle p_{i}\in \ell ^{+}}$ como ${\displaystyle q}$ lo es a ${\displaystyle \ell }$. Por tanto, el lugar geométrico de puntos más cercanos de algún sitio que a ${\displaystyle \ell }$ está limitado por una parábola. Siguiendo esta línea, el lugar geométrico de todos los puntos más cercanos a algún sitio sobre ${\displaystyle \ell }$ que a ${\displaystyle \ell }$ en sí misma está acotado por un conjunto de a lo más ${\displaystyle 2n-1}$[1]​ arcos parabólicos. Este conjunto de arcos se denomina línea de playa. Cada sitio ${\displaystyle p_{i}}$ sobre la línea de barrido define una parábola completamente. La línea de playa cuenta con la propiedad de monotonicidad ya que si se hace pasar cualquier recta vertical por ella, ésta la interseca en exactamente un punto.[1]​

Entonces, en lugar de mantener la intersección de ${\displaystyle Vor(P)}$ con ${\displaystyle \ell }$, se mantendrá la línea de playa conforme la línea de barrido se mueva. Evidentemente, no se puede representar explícitamente la línea de playa ya que es continua y se transforma cada que ${\displaystyle \ell }$ cambia de posición.

Generación de un nuevo arco en la línea de playa.

Un arco puede aparecer en la línea de playa cuando ${\displaystyle \ell }$ procesa un nuevo sitio, de ahí que esto tome el nombre de evento de sitio. En este momento una nueva parábola (en forma de línea vertical pues el lado recto es infinitesimalmente pequeño) rompe sobre la línea de playa. Conforme la línea de playa comienza a bajar, la recientemente creada parábola comienza a hacerse más amplía. Además, conforme va creciendo la parábola se generan intersecciones con otras parábolas en la línea de playa, lo cual comienza a trazar las aristas[1]​ del diagrama de Voronoi.

Un segundo evento de la línea de barrido surge cuando un arco ${\displaystyle \beta }$ se hace tan pequeño que se convierte en un punto. Cuando se presenta esto, las intersecciones que tenía ${\displaystyle \beta }$ con los otros arcos (${\displaystyle \beta '}$ a la izquierda y ${\displaystyle \beta ''}$ a la derecha) se juntan. Este encuentro de los puntos de intersección implica que dos aristas del diagrama se están encontrado. En consecuencia, se ha formado un vértice ${\displaystyle q}$ del diagrama de Voronoi. Gráficamente, ${\displaystyle q}$ es el centro de un círculo que pasa por los sitios ${\displaystyle p',p}$ y ${\displaystyle p''}$ correspondientes a ${\displaystyle \beta ',\beta }$ y ${\displaystyle \beta ''}$, respectivamente. Cuando ${\displaystyle \ell }$ alcanza el punto más bajo de este círculo, se ostenta un evento de círculo.

Estructuras de datos y algoritmo

El algoritmo de Fortune necesita de tres tipos de estructuras de datos:

1. Estructura de datos que ayude a guardar la porción del diagrama calculada hasta el momento. Para esto se emplea una lista doblemente conectada de aristas DCEL.[1]​ Se referirá a éste como ${\displaystyle {\mathcal {D}}}$.
2. Cola de prioridades ${\displaystyle {\mathcal {Q}}}$ que permita guardar los eventos de sitio y de círculo que debe procesar la línea de barrido.
3. Árbol de búsqueda binario balanceado ${\displaystyle {\mathcal {T}}}$ que guarde la línea de playa. Dado que no se puede guardar directamente la línea de playa debido a su naturaleza continua, se hace lo siguiente. En las hojas ${\displaystyle {\mathcal {T}}}$, se guardan los arcos de la línea de playa, caracterizados por el sitio que los define, manteniendo el orden como el que se apreciaría en la línea de playa realmente. Por su parte los nodos intermedios representan los puntos de quiebre (donde un arco rompe en la línea de playa) como túpalas ${\displaystyle <p_{i},p_{j}>}$, donde ${\displaystyle p_{i}}$ denota la parábola a la izquierda y ${\displaystyle p_{j}}$ la correspondiente a la derecha.

El siguiente pseudocódigo se basa en el que se presenta en la obra de Mark de Berg et al.[1]​

Algoritmo ${\displaystyle DiagramaVoronoi(P)}$

Entrada. Conjunto de sitios ${\displaystyle P={p_{1},\dots ,p_{n}}}$ en el plano.

Salida ${\displaystyle Vor(P)}$ dentro de una caja de restricción en ${\displaystyle {\mathcal {D}}}$.

Inicializar ${\displaystyle {\mathcal {Q}}}$ con todos los sitios; inicializar ${\displaystyle {\mathcal {T}}}$ como vacío y una DCEL ${\displaystyle {\mathcal {D}}}$ vacía.

while ${\displaystyle {\mathcal {Q}}}$ no esté vacía

Remover el evento con la coordenadana ${\displaystyle y}$ más grande de ${\displaystyle {\mathcal {Q}}}$.

if el evento es un evento de sitio en ${\displaystyle p_{i}}$ then

${\displaystyle ManejarEventoSitio(p_{i})}$

else ${\displaystyle ManejarEventoCirculo(\gamma )}$, donde ${\displaystyle \gamma }$ representa la hoja de ${\displaystyle {\mathcal {T}}}$ representando el arco que desaparecerá.

Computar caja de restricción que contenga todos los vértices de ${\displaystyle Vor(P)}$ dentro y una las semi-aristas hacia la caja.

${\displaystyle ManejarEventoSitio(p_{i})}$

Si ${\displaystyle {\mathcal {T}}}$ está vacío, insertar ${\displaystyle p_{i}}$. De lo contrario hacer los siguientes pasos.

Buscar en ${\displaystyle {\mathcal {T}}}$ el arco ${\displaystyle \alpha }$ verticalmente sobre ${\displaystyle p_{i}}$. Si la hoja ${\displaystyle \alpha }$ tiene un puntero hacia ${\displaystyle {\mathcal {Q}}}$, entonces es una falsa alarma y debe ser eliminado de ${\displaystyle {\mathcal {Q}}}$.

Reemplazar la hoja de ${\displaystyle {\mathcal {T}}}$ que representa a ${\displaystyle \alpha }$ con un subárbol con tres hojas. La hoja en el centro guarda el sitio ${\displaystyle p_{i}}$ y otras dos guardan a ${\displaystyle p_{j}}$ que originalmente estaba en ${\displaystyle \alpha }$. Guardar las túplas ${\displaystyle <p_{j},p_{i}>}$ y ${\displaystyle <p_{i},p_{j}>}$ representando los nuevos puntos de quiebre.

Crear nuevos registros de semi-aristas en ${\displaystyle {\mathcal {D}}}$ para la arista que separa a ${\displaystyle {\mathcal {V}}(p_{i})}$ y ${\displaystyle {\mathcal {V}}(p_{j})}$, que será trazada debido a los puntos de quiebre.

Checar las tripleta de arcos consecutivos donde el nuevo arco de ${\displaystyle p_{i}}$ es el arco izquierdo para ver si los puntos de quiebre convergen.

${\displaystyle ManejarEventoCirculo(\gamma )}$

Borrar la hoja ${\displaystyle \gamma }$ que representa el arco a desaparecer ${\displaystyle \alpha }$ de ${\displaystyle {\mathcal {T}}}$. Actualizar túplas que representan los puntos de quiebre. Reebalancear ${\displaystyle {\mathcal {T}}}$. Eliminar de ${\displaystyle {\mathcal {Q}}}$ todos los eventos que involucren a ${\displaystyle \alpha }$.

Añadir el centro del círculo causante del evento como un registro de vértice en ${\displaystyle {\mathcal {D}}}$. Crear dos semi-aristas correspondientes a los nuevos puntos de quiebre de la línea de playa.

Checar la nueva triplete de arcos consecutivos que tenía a ${\displaystyle \alpha }$ en el medio si los dos puntos de quiebre convergen. De ser así, insertarlo el evento correspondiente en ${\displaystyle {\mathcal {Q}}}$. Hacer lo mismo para la triplete donde ${\displaystyle \alpha }$ estaba a la derecha.

Complejidad

El algoritmo se ejecuta en ${\displaystyle O(n\log {n})}$ y usa ${\displaystyle O(n)}$ almacenamiento. Esto se debe a que las operaciones sobre ${\displaystyle {\mathcal {T}}}$ y en ${\displaystyle {\mathcal {Q}}}$ toman ${\displaystyle O(\log {n})}$.[4]​ Las operaciones en la DCEL toman tiempo constante.[1]​ Cuando se procesa un evento se ejecuta un número constante de operaciones de tales operaciones. Y dado que se tiene ${\displaystyle O(n)}$ eventos (debido al teorema 2), entonces la complejidad es ${\displaystyle O(n\log {n})}$. Por su parte, el almacenamiento es lineal nuevamente debido al teorema 2.

Generalización a ${\displaystyle \mathbb {R} ^{n}}$

Teselación de Voronói de un conjunto de puntos aleatorio sobre el plano.

Para cada conjunto topológico discreto S de puntos en un espacio euclídeo y para casi todo punto x, existe un punto de S que es el más cercano a x. (Aquí, el término casi se usa para indicar que existen excepciones en las cuales x puede equidistar de dos o más puntos de S.)

Si S contiene sólo dos puntos, a y b, entonces el conjunto de todos los puntos que equidistan de ambos es un hiperplano de codimensión 1. Ese hiperplano es la frontera entre los puntos más cercanos a a que a b, y los puntos más cercanos a b que a a. De hecho, ese hiperplano es el plano bisector del segmento que une a y b. Más en general, el conjunto de puntos más cercanos a un punto c de S que a ningún otro punto de S (cuenca de atracción de c) es el interior de un politopo convexo (posiblemente no acotado) llamado dominio de Dirichlet o celda de Voronói de c. El conjunto de todos esos politopos constituye una teselación completa del espacio euclídeo, llamada teselación de Voronói asociada a S.

Si la dimensión del espacio euclídeo es sólo 2, como en el plano euclídeo, entonces resulta muy sencillo dibujar teselaciones de Voronoi, como las de la figura adjunta.

Aplicaciones

Proceso llevado a cabo en un Sistema de Información Geográfica (SIG) para la obtención de ejes de calles mediante el uso de polígonos de Thiessen

Los diagramas de Voronoi encuentran aplicaciones en áreas tales como gráficos por computadora, geografía, epidemiología, geofísica y meteorología. Un uso particularmente notable fue en el análisis de la epidemia de cólera de 1854 en Londres llevado a cabo por el médico John Snow, el cual determinó una fuerte correlación de muertes con la proximidad a una determinada bomba de agua —a la postre contaminada— en Broad Street (en el distrito de Soho).[5]​ Su conocido mapa del cólera constituye hoy en día uno de los ejemplos clásicos de uso del método geográfico.

Se han utilizado para el análisis de datos meteorológicos (estaciones pluviométricas), aunque en la actualidad también se aplican en estudios en los que hay que determinar áreas de servicio (centros hospitalarios, estaciones de bomberos, bocas de metro, centros comerciales, control del tráfico aéreo, telefonía móvil, análisis de poblaciones de especies vegetales, etcétera). Es una de las funciones de análisis básicas en los Sistemas de Información Geográfica (SIG).

Una aplicación más avanzada es la de su uso en el geomarketing y el análisis geoespacial, para hacerlo primero se deben recopilar datos de latitud y longitud de los puntos que se requieren a estudiar, luego por medio de algoritmos no supervisados de machine learning como K-Means en conjunto con Voronoi sea pueden obtener clusters de dicho algoritmo no supervisado pero con la diferencia de que estos estarán delimitados por una región de Voronoi, entonces se puede obtener la "dominancia del cluster". Caso similar también aplica para el marketing, por ejemplo, en lugar de tener «latitud» o «longitud» de datos geoespaciales podríamos tener una relación entre ingresos de un grupo de usuarios y lo que suelen gastar, de forma que se pueda optimizar la publicidad de forma más eficiente usando la región de Voronoi como una ayuda extra para delimitar una publicidad de marketing a un grupo de usuarios.[6]​

Véase también

• Geometría euclídea
• Triangulación de Delaunay
• Aplicación de Voronoi en clusters de K-Means

Enlaces externos

• Geometría computacional, Departamento de Matemática Aplicada UPM
• Aplicaciones de arqueología a zoología
• Wiki de Voronói

Referencias

1. de Berg, Mark; Cheong, Otfried; van Kreveld, Marc; Overmars, Mark (2008). «7». Computational Geometry: Algorithms and Applications (en inglés) (tercera edición). Springer-Verlag Berlín Heidelberg. pp. 147-171. ISBN 978-3-540-77973-5. 
2. Preparata, Franco P.; Shamos, Michael Ian (1985). «5». En David Gries, ed. Computational Geometry: an introduction (en inglés). Springer-Verlag. pp. 204-223. ISBN 0-387-96131-3. 
3. Steven 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
4. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Clifford, Stein (2009). Introduction to Algorithms (en inglés) (tercera edición). MIT Press. ISBN 978-0-262-03384-8. 
5. http://mathworld.wolfram.com/VoronoiDiagram.html
6. «▷ Análisis geoespacial en Python: Cluster K-Means, Voronoi y Open Street Map». 16 de enero de 2024. Consultado el 1 de marzo de 2024. 

• Datos: Q757267
• Multimedia: Voronoi diagrams / Q757267