Fortune's algorithm

Pseudocode description of the algorithm.[4]

let ${\displaystyle *(z)}$ be the transformation ${\displaystyle *(z)=(z_{x},z_{y}+d(z))}$,
  where ${\displaystyle d(z)}$ is the Euclidean distance between z and the nearest site
let T be the "beach line"
let ${\displaystyle R_{p}}$ be the region covered by site p.
let ${\displaystyle C_{pq}}$ be the boundary ray between sites p and q.
let ${\displaystyle p_{1},p_{2},...,p_{m}}$ be the sites with minimal y-coordinate, ordered by x-coordinate
${\displaystyle Q\gets S-{p_{1},p_{2},...,p_{m}}}$
create initial vertical boundary rays ${\displaystyle C_{p_{1},p_{2}}^{0},C_{p_{2},p_{3}}^{0},...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},...,*(R_{p_{m-1}}),C_{p_{m-1},p_{m}}^{0},*(R_{p_{m}})}$

while not IsEmpty(Q) do
    p ← DeleteMin(Q)
    case p of
    p is a site in ${\displaystyle *(V)}$:
        find the occurrence of a region ${\displaystyle *(R_{q})}$ in T containing p,
          bracketed by ${\displaystyle C_{rq}}$ on the left and ${\displaystyle C_{qs}}$ on the right
        create new boundary rays ${\displaystyle C_{pq}^{-}}$ and ${\displaystyle C_{pq}^{+}}$ with bases p
        replace ${\displaystyle *(R_{q})}$ with ${\displaystyle *(R_{q}),C_{pq}^{-},*(R_{p}),C_{pq}^{+},*(R_{q})}$ in T
        delete from Q any intersection between ${\displaystyle C_{rq}}$ and ${\displaystyle C_{qs}}$
        insert into Q any intersection between ${\displaystyle C_{rq}}$ and ${\displaystyle C_{pq}^{-}}$
        insert into Q any intersection between ${\displaystyle C_{pq}^{+}}$ and ${\displaystyle C_{qs}}$
    p is a Voronoi vertex in ${\displaystyle *(V)}$:
        let p be the intersection of ${\displaystyle C_{qr}}$ on the left and ${\displaystyle C_{rs}}$ on the right
        let ${\displaystyle C_{uq}}$ be the left neighbor of ${\displaystyle C_{qr}}$ and
          let ${\displaystyle C_{sv}}$ be the right neighbor of ${\displaystyle C_{rs}}$ in T
        create a new boundary ray ${\displaystyle C_{qs}^{0}}$ if ${\displaystyle q_{y}=s_{y}}$,
          or create ${\displaystyle C_{qs}^{+}}$ if p is right of the higher of q and s,
          otherwise create ${\displaystyle C_{qs}^{-}}$
        replace ${\displaystyle C_{qr},*(R_{r}),C_{rs}}$ with newly created ${\displaystyle C_{qs}}$ in T
        delete from Q any intersection between ${\displaystyle C_{uq}}$ and ${\displaystyle C_{qr}}$
        delete from Q any intersection between ${\displaystyle C_{rs}}$ and ${\displaystyle C_{sv}}$
        insert into Q any intersection between ${\displaystyle C_{uq}}$ and ${\displaystyle C_{qs}}$
        insert into Q any intersection between ${\displaystyle C_{qs}}$ and ${\displaystyle C_{sv}}$
        record p as the summit of ${\displaystyle C_{qr}}$ and ${\displaystyle C_{rs}}$ and the base of ${\displaystyle C_{qs}}$
        output the boundary segments ${\displaystyle C_{qr}}$ and ${\displaystyle C_{rs}}$
    endcase
endwhile

output the remaining boundary rays in T