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

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.

author list (cited authors)

  • Lu, M.

publication date

  • December 1986