Voronoi-like nondeterministic partition of a lattice by collectives of finite automata

This paper describes an algorithm for the construction of the edges of a Vo ronoi diagram on a two-dimensional lattice by collectives of finite automat s which pick up and drop pebbles at nodes, and move at random between nodes . Given a set of labelled nodes on a lattice, we wish to identify those nod es of the lattice which are the edges of the Voronoi cells of the labelled nodes. Every finite automaton is given a color corresponding to one of the labelled nodes. Automats start their walks at the nodes of the given set. T hey carry pebbles, and change the orientations of their velocity vectors ac cording to a given probability distribution. When automats of different col ors meet at a node of the lattice they drop their pebbles. When this proces s has run its course, the number of pebbles of each color at each node of t he lattice indicates the membership degree (or probability of membership) o f this node in the set of edge nodes of the Voronoi diagram. In the paper, we analyse three models of the computation of Voronoi diagrams by automate, give results of numerical simulations, determine the convergence rate of t he algorithm, and show the exact shapes of the Voronoi cells. (C) 1998 Else vier Science Ltd. All rights reserved.