Notice: A non well formed numeric value encountered in M:\Shares\PalffyServer\elc\abstract.php on line 54

A Plane Sweep Algorithm for the Voronoi Tessellation of the Sphere

Xiaoyu Zheng ,Roland Ennis ,Gregory P. Richards ²,Peter Palffy-Muhoray ³
Department of Mathematical Sciences,Kent State University, Kent, OH 44242, USA Pressco Technology, Inc, Cleveland, Ohio 44139, USA ²Deparment of Mathematical Sciences and Liquid Crystal Institute, Kent State University, Kent, Ohio 44242, USA ³Liquid Crystal Institute, Kent State University, Kent, Ohio, 44242, USA
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