A. Adamatzky / Physics Letters A 374 (2009) 264–271
265
computing the Voronoi diagram. In Section 4 we show how to
extract direction towards the site of crystallization induction. Com-
putation of one-destination-many-sources paths by crystallization
of sodium acetate, and further extraction of a collision-free short-
est path, are discussed in Section 5. Experimental implementation
of logical gates is presented in Section 6. We summarize the find-
ings and discuss further developments in Section 7.
acetate propagate much quicker and thus could improve speed lim-
itations of existing reaction–diffusion algorithms.
We represented data points of set P by a configuration of pins
(pieces of aluminum wire) fixed through the lid of a 9 cm Petri
dish (Fig. 1(a)). The pins were powdered with fine crystals of
sodium acetate.
To start computation we place the lid on the dish with the
supersaturated solution. The pins become immersed into the so-
lution. They induce crystallization. Patterns of crystallization prop-
agate — as classical target waves — from the sites of crystallization
induction.
2. Methods
We prepare a supersaturated clear solution of sodium acetate
A crystallization wave stops when it encounters another wave
of crystallization (Fig. 1(b) and (c)). Boundaries between station-
ary patterns of crystallization represent edges of planar Voronoi
diagram VD(P). The experimental boundaries perfectly correspond
to bisectors of the diagram computed by the classical Fortune’s
sweepline algorithm [21] (Fig. 1(d)).
trihydrate CH3COONa·3H2O, pour the hot solution into Petri dishes
◦
and cool the solution down to −5 C. To induce crystallization we
briefly immerse aluminum wire (powdered with fine crystals of
the sodium acetate) into the solution.
To compute shortest paths in a space with obstacles we mimic
obstacles with blobs of silicon, small Petri dishes fixed to the bot-
tom of experimental container and labyrinths made of Blu-Tack®.1
Dynamics of crystallization is recorded with FujiPix 6000 digital
camera and still high-resolution images are produced by scanning
containers with crystallized sodium acetate in HP Deskjet 5100
scanner. Magnified images of the crystalline structure formed are
taken using Digital Blue® QX-5 USB microscope.
4. Detecting directions towards sites of crystallization induction
Crystals growing from nucleation sites bear distinctive elon-
gated shapes expanding towards their proximal ends (Fig. 2(a)).
Not only a crystal’s overall shape but also the orientation of saw-
tooth edges indicate the direction of the crystal’s growth (Fig. 2(b)).
The direction of crystal growth can be detected by conven-
tional image processing techniques, e.g. edge detection procedures
(Fig. 2), or by a complementary method of detecting directional
uniformity of image domains as discussed below.
Software tools for extracting directions of crystal growth from
still images and models of cellular-automaton shortest path calcu-
lation are coded in Processing.2
3. Voronoi diagram
We detect local directions of crystal grows in the following way.
A fine grid of nodes is applied onto given image and for every
node x of the grid we calculate a set V of vectors of length r
originating at x and directed at angles α ∈ {0, 0.1, 0.2, ... , 2/π}.
For each vector v ∈ V we calculate a sum of standard deviations
σꢁ(v) of RGB colors of the image pixels coinciding with v. A vector
v = minv∈V σ(v) with minimal sum of color deviations indicates
a local direction of crystallization propagation. A configuration of
local direction vectors, r = 20, is shown in Fig. 2(d).
Let P be a nonempty finite set of planar points. A planar
Voronoi diagram of P is a partition of the plane into such regions,
that for any element of P, a region corresponding to a unique point
p contains all those points of the plane which are closer to p than
to any other node of P. A unique region vor(p) = {z ∈ R2: d(p, z) <
d(p,m) ∀m ∈ R2, m ꢀ= z} assigned to point p is called a Voronoi
cell of the point p. The boundary of the Voronoi cell of a point p
is built of segments of bisectors separating pairs of geographically
closest points of the given planar set P. A union of all bound-
The vector configuration represents sinks determined by points
from set P. If we place a mobile agent at any site but bisectors
of the vector configuration Fig. 2(d) the agent will be attracted to
the closest data point p. This leads us to another problem solvable
with sodium acetate — computation of a collision-free shortest
path in a space with obstacles.
aries of the Voronoi cells determines the planar Voronoi diagram:
ꢀ
VD(P) = p∈P ∂vor(p) [16,17].
A basic concept of parallel approximation of Voronoi diagram
by wave patterns propagating in a spatially extended medium [18]
is based on time-to-distance transformation. To compute a bisector
separating two given points p and q we initiate wave-patterns in
the medium’s sites geographically corresponding to p and q. The
waves travel the same distance from the sites of origination be-
fore colliding. The loci where the waves meet indicate sites of the
computed bisector.
5. Computation of a collision-free path
Previously [22] we have designed a cellular-automaton algo-
rithm for constructing one-destination-many-sources shortest path.
The automaton is a regular array of finite state machines (cells)
which takes discrete states and update their states simultaneously
and in discrete time depending on the states of its closest neigh-
bors. Here we consider hexagonal array of cells. Each cell has six
neighbors and takes three states — resting, excited and refrac-
tory. A resting cell becomes excited if it has at least one excited
neighbor. An excited cell switches to a refractory state, and re-
fractory cell returns to resting state independently on states of its
neighbors. When we excite one cell of a resting array a wave of
excitation is initiated. The excitation wave propagates in the array.
To store the computed path we supply every cell with a pointer.
Pointers in all cells are set to nil initially. When a cell becomes
excited its pointer orients towards the direction from where the
excitation wave came. An example is shown in Fig. 3(a).
Precipitating reaction–diffusion chemical media are proved to
be an ideal computing substrate for approximation of the planar
Voronoi diagram [4,19,20]. A Voronoi diagram can be approxi-
mated in a two-reagent medium. One reagent α is saturated in the
substrate, drops of another reagent β are applied to the sites corre-
sponding to planar points to be separated by bisectors. The reagent
β diffuses in the substrate and reacts with reagent α. Colored pre-
cipitate is produced in the reaction between α and β. When two
or more waves of diffusing α meet, no precipitate is formed [20].
Thus uncolored loci of the reaction–diffusion medium represent bi-
sectors of the computed diagram.
Most reaction–diffusion chemical processors are quite slow in
computing a Voronoi diagram at the macro-scale, due to speed
limitations caused by diffusion. Crystallization patterns in sodium
Obstacles are imitated by always-resting, or non-excitable, cells.
Examples of the pointer configuration and shortest collision-free
paths are shown in Fig. 3(b). A cell assigned to be a destination (in
the north-west corner of the array Fig. 3(b)) is excited. Waves of
1
2