Parallel algorithms to find the Voronoi diagram and the order-k Voronoi diagram

The Voronoi diagram is a classical problem in the area of computational geometry. Given a plane and a set of n seed points, the objective is to divide the plane into tiles (or subsets of points), such that the set of points in a tile are closer to a particular seed point than to any other seed. This problem has become increasingly important in the area of geographic information systems (GIS) as Voronoi diagrams are used in GIS for computing zonal statistics. Current or timely data for GIS is acquired via remotely-sensed devices providing data in raster(regular or gridded) format. This paper describes parallel algorithms to find the Voronoi Diagram, the furthest site Voronoi diagram and the order-k Voronoi diagram. Prototype implementations in Parallaxes are outlined.