Constructing the Voronoi Diagram on a Mesh-Connected Computer
Lu, Mi · Figshare · 2021
In this paper, we present a Mesh-Connected Computer algorithm to construct the Voronoi diagram of a set of planar points. Given a set of n planar points our algorithm constructs a Voronoi diagram on an O (√n x √n) MCC with the constant storage per processer in O(√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. Previous known parallel algorithm for this problem requires O(log3n) time on a Parallel Random Access Machine and O(log4n) time on the Cube-Connected-cycles with O(log n) storage per PE.