R.B. Muhammad (USA)
Voronoi diagram, dividing chain, hypercube, and intersec tion set.
The Voronoi diagram of a set of n sites on the plane has application in many diverse areas such as Geograph ical Information Systems (GIS), Visualization, Robotics, Computer Graphics and Computer Aided Design (CAD). Unfortunately, its construction is very costly for large in put sizes, and fast parallel algorithms for the problem are desired. There are no known parallel algorithms for the problem that are optimal with respect to the time-processor product. Best sequential algorithms work in O(n lg(n)) time. In this paper, an O(lg3 n) time parallel algorithm for constructing the Voronoi Diagram of a set of n sites in the plane is presented on a hypercube with n processors. Our technique parallelizes the well-known seemingly inherent sequential technique of Shamos and Hoey, and makes use of a number of special properties of the dividing polygonal chain and the Batcher's bitonic sort.
Important Links:
Go Back
