DocumentCode
1405768
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
Volume
8
Issue
11
fYear
1997
fDate
11/1/1997 12:00:00 AM
Firstpage
1133
Lastpage
1142
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;
fLanguage
English
Journal_Title
Parallel and Distributed Systems, IEEE Transactions on
Publisher
ieee
ISSN
1045-9219
Type
jour
DOI
10.1109/71.642948
Filename
642948
Link To Document