Title :
A simple Voronoi diagram algorithm for a reconfigurable mesh
Author :
Elgindy, Hossam ; Wetherall, Lachlan
Author_Institution :
Dept. of Comput. Sci., Newcastle Univ., NSW, Australia
fDate :
11/1/1997 12:00:00 AM
Abstract :
In this paper, we introduce a simple and efficient algorithm for computing the Voronoi Diagram for n planar points on a reconfigurable mesh of size O(n)×O(n). The algorithm has a worst case running of O(log n log log n) time. The algorithm exploits the O(1) communication diameter of the reconfigurable mesh model to implement efficient load balancing
Keywords :
computational complexity; computational geometry; parallel algorithms; parallel architectures; reconfigurable architectures; O(1) communication diameter; Voronoi diagram algorithm; broadcasting buses; geometric algorithms; load balancing; n planar points; parallel algorithms; reconfigurable mesh; reconfigurable mesh architectures; Australia; Broadcasting; Communication switching; Communication system control; Computational modeling; Concurrent computing; Load management; Partitioning algorithms; Region 5; Switches;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
