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

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.

authors

• Lu, Mi

published proceedings

• Proceedings of the International Conference on Parallel Processing

author list (cited authors)

• Lu, M.

complete list of authors

• Lu, M

publication date

• December 1986

published in

• Proceedings of the International Conference on Parallel Processing  Journal

International Standard Book Number (ISBN) 10

• 0818607246

start page

• 806

end page

• 811