CONSTRUCTING THE VORONOI DIAGRAM ON A MESH-CONNECTED COMPUTER.
Conference Paper

Overview

Identity

Additional Document Info

View All

Overview

abstract

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.