3.5 Plane Subdivision

3.5 Plane Subdivision

Let P be a nonempty finite set of planar points—a Voronoi diagram of the set P is a partition of the plane into such regions, each for any element of P, that a region corresponding to a unique point p contains all those points of the plane that are closer to p than to any other node of P. A unique region assigned to point p is called a Voronoi cell of the point p; a union of all the edges of the Voronoi cells determines the Voronoi diagram.

Assuming the computing space is homogeneous and locally connected ( la cellular automata, where every node is coupled to its closest neighbors by the same diffusive links), we can easily draw a parallel between the distance and the time. There is a very simple intuitive technique for detecting the bisector points separating two given points of the set P. If we drop reagents at these two nodes, the diffusive waves (or phase waves if an active substrate) spread outward from the originating points with the same speed; they travel the same distance from the sites of origination before they meet with one another. The points where the waves meet are the bisector points.

In a naive version of reaction-diffusion computing of a Voronoi diagram, one needs two reagents and a precipitate to mark a bisector separating two points—that is, n reagents are required to approximate a Voronoi diagram of n points. We place n unique reagents on n points of the given set; waves of these reagents spread around the space and interact with each other when they meet. When at least two different reagents meet at the same or adjacent sites of the space, they react and form a precipitate, resulting in: the reaction-sites that contain the precipitate represent edges of the Voronoi cell and therefore constitute the Voronoi diagram. Actually, the number of reagents can be sufficiently reduced (literally to just two states) in cellularautomaton models: when the topology of the spreading waves of the excitation is taken into account (Adamatzky 2001), and in real experimental wet processors (Tolmachev and Adamatzky 1996; Adamatzky and De Lacy Costello 2002a).

In cellular-automaton models (Adamatzky 2001), a colored precipitate is formed when chemical waves collide with each other: colored sites are sites of Voronoi diagram edges, uncolored sites are simply "planar points". If we try to implement this idea in a real chemical medium, we find an even simpler solution: when two or more wave fronts collide, no colored precipitate will form at sites of their collision, while all other parts of the medium are colored with the precipitate. Thus the Voronoi diagram is represented by light (or uncolored) loci of the chemical medium.

A palladium processor (Tolmachev and Adamatzky 1996; Adamatzky and De Lacy Costello 2002a, 2002b) is a first-ever specialized chemical computer after Belousov-Zhabotinsky processors (see, e.g., Kuhnert, Agladze, and Krinsky 1986; Rambidi and Chernavskii 1991; Rambidi, Maximychev, and Usatov 1994; Rambidi et al. 2002) to be used for image processing and computational geometry. An active planar substrate is prepared by mixing agar gel with a solution of palladium chloride. This thin film of agar is placed on an acetate film. Sites corresponding to the planar points, which must be subdivided by Voronoi bisectors, are marked by drops of potassium iodide solution. The potassium iodide diffuses from the given points and fills almost the entire reaction space with a dark color, because a precipitate of palladium iodide is produced as the result of the reaction. When two diffusive wave fronts meet with one another, no precipitate is formed (this may happen due to exhaustion of potassium iodide, or concentration inhibition of the reaction, or even physical interaction—e.g., repulsion—of the diffusive fronts). Thus the bisectors of the Voronoi diagram are represented by colorless zones of the reaction space, as shown in figure 3.1.

Figure 3.1: Voronoi diagram, constructed in experimental reaction-diffusion processor. Bisectors are seen as light (uncolored) segments. Original data points are represented by light discs. (With permission of Benjamin de Lacy Costello, Bristol, UK.)