Fortune’s algorithm on a sphere.
n = 100 sites
n = 20 sites
n = 4 sites
n = 3 sites
Note that n = 4 is the minimum number of sites required to avoid producing spherical digons which cannot be represented using mesh subdivision techniques. (At n = 2, the voronoi diagram consists of two unigonal hemispheres, and at n = 1 it is a single 0-gon encompassing the entire globe.)
The following screenshots are from before spherical mesh subdivision was implemented:
n = 600 sites
n = 6000 sites