FINE-GRAIN DISCRETE VORONOI-DIAGRAM ALGORITHMS IN L-1 AND L-INFINITY NORMS

The well-known Voronoi diagram problem partitions a space containing a finite set of points, P, in such a way that each partition contains a single point in P and the subspace for which it is the nearest point from the set. Adamatzky defined the Discrete Voronoi Diagram (DVD) pro blem as finding the Voronoi diagram in a discrete lattice. Adamatzky p roposed some efficient algorithms for computing DVDs on fine grained s ynchronous single instruction multiple data (SIMD) mesh architectures when either the L-1 or the L-infinity distance metric is used. This pa per presents improvements to Adamatzky's algorithms that ensure their correctness without increasing their complexity.