Voronoi-like partition of lattice in cellular automata

In this paper, we discuss an automata model for parallel approximation of the discrete Voronoi diagram. Given a subset of the n labeled nodes of two-dimensional lattice of m × m nodes, we wish to construct a Voronoi cell for every given node, i.e., mark such nodes that form Voronoi edges and vertices. Our technique is based on the wave generation in the cellular automata lattice, their spreading and interaction. The waves are generated in such sites that are corresponded to lattice nodes of a given set (which should be separated). In the result of wave interactions a stationary structure is produced—it represents the required elements of the discrete Voronoi diagram. We show how to construct Voronoi-like structure in two-dimensional cellular automata with O(1) and O(n) cell states and 4 (in metric L1) or 8 (in metric l∞) size of cell neighborhood in O(m) time.