El algoritmo de Fortune

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

Sea la transformación , donde es la distancia euclidiana entre z y el sitio más cercano. Sea T la "línea de playa". Sea la región cubierta por el sitio p . Sea el rayo límite entre los sitios p y q . Sea un conjunto de sitios sobre los que se aplicará este algoritmo. Sean los sitios extraídos de S con la coordenada y mínima , 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. Crear rayos límite verticales iniciales.${\displaystyle \scriptstyle *(z)}$${\displaystyle \scriptstyle *(z)=(z_{x},z_{y}+d(z))}$${\displaystyle \scriptstyle d(z)}$${\displaystyle \scriptstyle R_{p}}$${\displaystyle \scriptstyle C_{pq}}$${\displaystyle \scriptstyle S}$${\displaystyle \scriptstyle p_{1},p_{2},...,p_{m}}$${\displaystyle Q\gets {p_{1},p_{2},\dots ,p_{m},S}}$${\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 en T que contenga p ,${\displaystyle \scriptstyle *(R_{q})}$ entre paréntesis por a la izquierda y a la derecha crea nuevos rayos límite y con bases p reemplaza con en T elimina de Q cualquier intersección entre e inserta en Q cualquier intersección entre e inserta en Q cualquier intersección entre y p es un vértice de Voronoi en : sea p la intersección de a la izquierda y a la derecha sea el vecino izquierdo de y sea el vecino derecho de en T si , crea un nuevo rayo límite sino si p está a la derecha del mayor de q y s , crea sino crea fin si reemplaza con recién creado en T elimina de Q cualquier intersección entre y elimina de Q cualquier intersección entre e inserta en Q cualquier intersección entre e inserta en Q cualquier intersección entre y registra p como la cima de y y la base de imprime los segmentos límite y fin caso fin mientras${\displaystyle \scriptstyle C_{rq}}$${\displaystyle \scriptstyle C_{qs}}$${\displaystyle \scriptstyle C_{pq}^{-}}$${\displaystyle \scriptstyle C_{pq}^{+}}$${\displaystyle \scriptstyle *(R_{q})}$${\displaystyle \scriptstyle *(R_{q}),C_{pq}^{-},*(R_{p}),C_{pq}^{+},*(R_{q})}$${\displaystyle \scriptstyle C_{rq}}$${\displaystyle \scriptstyle C_{qs}}$${\displaystyle \scriptstyle C_{rq}}$${\displaystyle \scriptstyle C_{pq}^{-}}$${\displaystyle \scriptstyle C_{pq}^{+}}$${\displaystyle \scriptstyle C_{qs}}$${\displaystyle \scriptstyle *(V)}$${\displaystyle \scriptstyle C_{qr}}$${\displaystyle \scriptstyle C_{rs}}$${\displaystyle \scriptstyle C_{uq}}$${\displaystyle \scriptstyle C_{qr}}$${\displaystyle \scriptstyle C_{sv}}$${\displaystyle \scriptstyle C_{rs}}$${\displaystyle \scriptstyle q_{y}=s_{y}}$${\displaystyle \scriptstyle C_{qs}^{0}}$${\displaystyle \scriptstyle C_{qs}^{+}}$${\displaystyle \scriptstyle C_{qs}^{-}}$${\displaystyle \scriptstyle C_{qr},*(R_{r}),C_{rs}}$${\displaystyle \scriptstyle C_{qs}}$${\displaystyle \scriptstyle C_{uq}}$${\displaystyle \scriptstyle C_{qr}}$${\displaystyle \scriptstyle C_{rs}}$${\displaystyle \scriptstyle C_{sv}}$${\displaystyle \scriptstyle C_{uq}}$${\displaystyle \scriptstyle C_{qs}}$${\displaystyle \scriptstyle C_{qs}}$${\displaystyle \scriptstyle C_{sv}}$${\displaystyle \scriptstyle C_{qr}}$${\displaystyle \scriptstyle C_{rs}}$${\displaystyle \scriptstyle C_{qs}}$${\displaystyle \scriptstyle C_{qr}}$${\displaystyle \scriptstyle C_{rs}}$ 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 encontrado que el algoritmo tiene una complejidad temporal donde n es el número de sitios según la referencia ^{[ 1 ] .}${\displaystyle O(n\log(n))}$

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.