DocumentCode
2634405
Title
A simple Voronoi diagram algorithm for a reconfigurable mesh
Author
ElGindy, Ilossam ; Wetherall, Lachlan
Author_Institution
Dept. of Comput. Sci., Newcastle Univ., NSW, Australia
fYear
1995
fDate
25-28 Apr 1995
Firstpage
296
Lastpage
303
Abstract
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(logn log logn) time, and O(logn) in practice. The algorithm exploits the O(1) communication diameter of the reconfigurable mesh model to implement efficient load balancing
Keywords
computational geometry; reconfigurable architectures; scheduling; Voronoi diagram algorithm; communication diameter; load balancing; planar points; reconfigurable mesh; worst case running; Australia; Computer networks; Computer science; Concurrent computing; Councils; Load management; Partitioning algorithms; Scholarships; Switches; Writing;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel Processing Symposium, 1995. Proceedings., 9th International
Conference_Location
Santa Barbara, CA
Print_ISBN
0-8186-7074-6
Type
conf
DOI
10.1109/IPPS.1995.395948
Filename
395948
Link To Document