We have extended Fortune's sweep-line algorithm for the construction Voronoi diagrams in the plane to the surface of a sphere. Although the extension is straightforward, it requires interesting modi¯cations. The main di®erence between the sweep line algorithms on plane and on the sphere is that that the beach line on the sphere is a closed curve. We have implemented this algorithm and tessellated spheres with up to one million sites. The running time for our sweep line algorithm on the sphere is O(N logN), and the storage space is O(N).

Full Document