Article Preview
Top1. Introduction
Voronoi diagrams are a partitioning of continuous space into regions. The regions are constructed about a finite set of distinct isolated points. Therefore, all locations within the space are associated with the closest member of the point set (Okabe et al., 2009). Thus, Voronoi diagrams have utility as modelling tools where space should be segregated into “spheres of influence.” They find uses in many fields such as astronomy (galaxy cluster analysis (Pastzor & Csillag, 1994)), biology (modelling tumour cell growth (Blackburn & Dunckley, 1996)), chemistry (modelling crystal growth (Hargittai, 1986), ecology (modelling competition (Byers, 1992) and computational geometry (solving nearest neighbor problems (Graham & Yao, 1990). In addition to standard and generalized Voronoi diagrams (where geometric shapes rather than point sources are utilized) weighted diagrams are commonly used, for example, to model crystal growth (Scaudt & Drysdale, 1991).
In addition to their many uses in modelling, Voronoi diagrams can be observed widely in nature, for example, in animal coat markings (Walter et al., 1998) between interacting bacterial, fungal or slime mould colonies (Aurenhammer, 1991; Muller et al., 1998, Shirikawa et al., 2009), between growing crystals (de Lacy Costello et al., 2010) and even in universal structures such as gravitational caustics (Stevens, 1979). They have also been observed and constructed within Gas discharge systems (Zanin et al., 2002 and de Lacy Costello et al., 2004).
The formation of Voronoi diagrams in chemical systems with one reagent and one substrate was first reported by (Tolmachiev & Adamatzky, 1996). This and similar reactions were utilized as chemical processors for the computation of the shortest obstacle free path (Adamatzky & de Lacy Costello, 2003), the skeletonization of a planar shape (Adamatzky & Tolmachiev, 1997; Adamatzky et al., 2002) and the construction of a prototype XOR gate (Adamatzky & de Lacy Costello, 2002). The formation of weighted Voronoi diagrams from two reagents reacted in parallel on one substrate were first reported in (de Lacy Costello, 2003). In the same year the calculation of three Voronoi diagrams in parallel was reported in a chemical system based on the reaction of two reagents on a mixed substrate gel (potassium ferrocyanide and potassium ferricyanide) (de Lacy Costello & Adamatzky, 2003). Complex tessellations of the plane have been constructed in simple chemical reactions where one of two binary reagents exhibited limited or no reactivity with the gel substrate (de Lacy Costello et al., 2009). A more recent paper investigated complex tessellations arising from three reagents on certain substrate loaded gels (de Lacy Costello et al., 2010).