El algoritmo de Fortune

Descripción en pseudocódigo del algoritmo. ^{[ 4 ]}

dejar${\displaystyle \scriptstyle *(z)}$ser la transformación${\displaystyle \scriptstyle *(z)=(z_{x},z_{y}+d(z))}$, dónde${\displaystyle \scriptstyle d(z)}$es la distancia euclidiana entre z y el sitio más cercano sea T la "línea de playa" sea${\displaystyle \scriptstyle R_{p}}$Sea la región cubierta por el sitio p . ${\displaystyle \scriptstyle C_{pq}}$Sea el rayo límite entre los sitios p y q . ${\displaystyle \scriptstyle S}$Sea un conjunto de sitios en los que se aplicará este algoritmo. ${\displaystyle \scriptstyle p_{1},p_{2},...,p_{m}}$Sea X el conjunto de sitios extraídos de S con la mínima coordenada y , ordenados por la coordenada x. Sea DeleteMin( X ) la acción de eliminar el sitio más bajo y el más a la izquierda de X (ordenar por y a menos que sean idénticos, en cuyo caso ordenar por x). Sea V el mapa de Voronoi de S que se construirá mediante este algoritmo. ${\displaystyle Q\gets {p_{1},p_{2},\dots ,p_{m},S}}$crear rayos límite verticales iniciales${\displaystyle \scriptstyle C_{p_{1},p_{2}}^{0},C_{p_{2},p_{3}}^{0},\dots ,C_{p_{m-1},p_{m}}^{0}}$${\displaystyle T\gets *(R_{p_{1}}),C_{p_{1},p_{2}}^{0},*(R_{p_{2}}),C_{p_{2},p_{3}}^{0},\dots ,*(R_{p_{m-1}}),C_{p_{m-1},p_{m}}^{0},*(R_{p_{m}})}$mientras no IsEmpty( Q ) hacer p ← DeleteMin( Q ) caso p de p es un sitio en${\displaystyle \scriptstyle *(V)}$: encontrar la ocurrencia de una región${\displaystyle \scriptstyle *(R_{q})}$en T que contiene p , entre paréntesis por${\displaystyle \scriptstyle C_{rq}}$a la izquierda y${\displaystyle \scriptstyle C_{qs}}$A la derecha se crean nuevos rayos límite${\displaystyle \scriptstyle C_{pq}^{-}}$y${\displaystyle \scriptstyle C_{pq}^{+}}$con bases p reemplazar${\displaystyle \scriptstyle *(R_{q})}$con${\displaystyle \scriptstyle *(R_{q}),C_{pq}^{-},*(R_{p}),C_{pq}^{+},*(R_{q})}$en T eliminar de Q cualquier intersección entre${\displaystyle \scriptstyle C_{rq}}$y${\displaystyle \scriptstyle C_{qs}}$insertar en Q cualquier intersección entre${\displaystyle \scriptstyle C_{rq}}$y${\displaystyle \scriptstyle C_{pq}^{-}}$insertar en Q cualquier intersección entre${\displaystyle \scriptstyle C_{pq}^{+}}$y${\displaystyle \scriptstyle C_{qs}}$p es un vértice de Voronoi en${\displaystyle \scriptstyle *(V)}$: sea p la intersección de${\displaystyle \scriptstyle C_{qr}}$a la izquierda y${\displaystyle \scriptstyle C_{rs}}$a la derecha deja${\displaystyle \scriptstyle C_{uq}}$ser el vecino izquierdo de${\displaystyle \scriptstyle C_{qr}}$y dejar${\displaystyle \scriptstyle C_{sv}}$ser el vecino adecuado de${\displaystyle \scriptstyle C_{rs}}$en T si${\displaystyle \scriptstyle q_{y}=s_{y}}$, crea un nuevo rayo límite${\displaystyle \scriptstyle C_{qs}^{0}}$de lo contrario, si p está a la derecha del mayor de q y s , crea${\displaystyle \scriptstyle C_{qs}^{+}}$de lo contrario crear${\displaystyle \scriptstyle C_{qs}^{-}}$fin si reemplazar${\displaystyle \scriptstyle C_{qr},*(R_{r}),C_{rs}}$con recién creado${\displaystyle \scriptstyle C_{qs}}$en T eliminar de Q cualquier intersección entre${\displaystyle \scriptstyle C_{uq}}$y${\displaystyle \scriptstyle C_{qr}}$eliminar de Q cualquier intersección entre${\displaystyle \scriptstyle C_{rs}}$y${\displaystyle \scriptstyle C_{sv}}$insertar en Q cualquier intersección entre${\displaystyle \scriptstyle C_{uq}}$y${\displaystyle \scriptstyle C_{qs}}$insertar en Q cualquier intersección entre${\displaystyle \scriptstyle C_{qs}}$y${\displaystyle \scriptstyle C_{sv}}$ registro p como la cima de${\displaystyle \scriptstyle C_{qr}}$y${\displaystyle \scriptstyle C_{rs}}$y la base de${\displaystyle \scriptstyle C_{qs}}$ generar los segmentos de límite${\displaystyle \scriptstyle C_{qr}}$y${\displaystyle \scriptstyle C_{rs}}$fin de caso fin mientras generar los rayos límite restantes en T

Como describe Fortune en la referencia ^{[ 1 ],} se puede utilizar una versión modificada del algoritmo de línea de barrido para construir un diagrama de Voronoi ponderado aditivamente , en el que la distancia a cada sitio se compensa con el peso del sitio; esto puede verse equivalentemente como un diagrama de Voronoi de un conjunto de discos, centrados en los sitios con un radio igual al peso del sitio. Se ha descubierto que el algoritmo tiene${\displaystyle O(n\log(n))}$complejidad temporal donde n es el número de sitios según la referencia ^{[ 1 ]}

Los puntos ponderados pueden utilizarse para controlar las áreas de las celdas de Voronoi al construir diagramas de Voronoi para mapas de árbol . En un diagrama de Voronoi con ponderación aditiva, la bisectriz entre puntos es, en general, una hipérbola, a diferencia de los diagramas de Voronoi sin ponderación y los diagramas de potencia de discos, para los cuales es una línea recta.