Fortune's algorithm

Pseudocode description of the algorithm.[4]

let ${\displaystyle \scriptstyle *(z)}$ be the transformation ${\displaystyle \scriptstyle *(z)=(z_{x},z_{y}+d(z))}$,
  where ${\displaystyle \scriptstyle d(z)}$ is the Euclidean distance between z and the nearest site
let T be the "beach line"
let ${\displaystyle \scriptstyle R_{p}}$ be the region covered by site p.
let ${\displaystyle \scriptstyle C_{pq}}$ be the boundary ray between sites p and q.
let ${\displaystyle \scriptstyle S}$ be a set of sites on which this algorithm is to be applied.
let ${\displaystyle \scriptstyle p_{1},p_{2},...,p_{m}}$ be the sites extracted from S with minimal y-coordinate, ordered by x-coordinate
let DeleteMin(X) be the act of removing the lowest and leftmost site of X (sort by y unless they're identical, in which case sort by x) 
let V be the Voronoi map of S which is to be constructed by this algorithm
${\displaystyle Q\gets {p_{1},p_{2},\dots ,p_{m},S}}$
create initial vertical boundary rays ${\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}})}$

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

output the remaining boundary rays in T

As Fortune describes in ref.,[1] a modified version of the sweep line algorithm can be used to construct an additively weighted Voronoi diagram, in which the distance to each site is offset by the weight of the site; this may equivalently be viewed as a Voronoi diagram of a set of disks, centered at the sites with radius equal to the weight of the site. the algorithm is found to have ${\displaystyle O(n\log(n))}$ time complexity with n being the number of sites according to ref.[1]

Weighted sites may be used to control the areas of the Voronoi cells when using Voronoi diagrams to construct treemaps. In an additively weighted Voronoi diagram, the bisector between sites is in general a hyperbola, in contrast to unweighted Voronoi diagrams and power diagrams of disks for which it is a straight line.