CONSTRUCTING THE VORONOI DIAGRAM ON A MESH-CONNECTED COMPUTER.
- Additional Document Info
- View All
A mesh-connected computer (MCC) algorithm is presented to construct the Voronoi diagram of a set of planar points. Given a set of n planar points, the algorithm constructs a Voronoi diagram on an O( ROOT n multiplied by ROOT n) MCC with constant storage per processor in O( ROOT n log n) time. Using the Voronoi diagram, the problem of determining the nearest neighbor between two sets and constructing the Euclidean minimum spanning trees can be solved with the same time complexity on the MCC. The best sequential algorithms for constructing the Voronoi diagram have an optimal O(n log n) time complexity. The previously known parallel algorithm for this problem requires O(log**3 n) time on a parallel random access machine and O(log**4 n) on the cube-connected-cycles with O(log n) storage per PE.
Proceedings of the International Conference on Parallel Processing
author list (cited authors)
complete list of authors