A SIMPLE VORONOI DIAGRAM ALGORITHM FOR A RECONFIGURABLE MESH

Authors
ELGINDY H WETHERALL L
Citation
H. Elgindy et L. Wetherall, A SIMPLE VORONOI DIAGRAM ALGORITHM FOR A RECONFIGURABLE MESH, IEEE transactions on parallel and distributed systems, 8(11), 1997, pp. 1133-1142
Citations number
35
Categorie Soggetti
System Science","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
Journal title
IEEE transactions on parallel and distributed systems → ACNP
ISSN journal
10459219
Volume
8
Issue
11
Year of publication
1997
Pages
1133 - 1142
Database
ISI
SICI code
1045-9219(1997)8:11<1133:ASVDAF>2.0.ZU;2-5
Abstract
In this paper, we introduce a simple and efficient algorithm for compu ting the Voronoi Diagram for n planar points on a reconfigurable mesh of size O(n) x O(n). The algorithm has a worst case running of O(log n log log n) time. The algorithm exploits the O(1) communication diamet er of the reconfigurable mesh model to implement efficient load balanc ing.