Cellular Automaton Performing TwoColoring of Square Tiled Planes
Jiri Kroc University of West Bohemia Helsinki School of Economics
The main goal of this work is to show on a simple periodic case—and easy to simulate—that there exists a
class of cellular automata, possibly deterministic, enabling us to effectively perform the coloring of tiled planes.
Similar algorithms—where determinism is in question—could be applied to the threeneighbor case on square
grids and to aperiodic or quasiperiodic threeneighbor tilings, and for example, the Penrose tiling.
A rule which performs a coloring of tiles ensures that no two neighboring tiles have the same color. A 2D deterministic cellular automaton is defined and performs a twocoloring of squares in the plane using selforganization.
Antiphase separation boundaries lie between two regions, inside of which all tiles are correctly colored with respect to each other, but the boundary itself is out of the order. They naturally emerge from random and nonrandom initial conditions, and their presence could lead to more than two times longer the total simulation time.
Appearance of such antiphase separation borders could be protected by use of a special initial condition consisting of one seed—located in the leftlower corner in our case. Seed has one color and is immersed into the homogeneous ‘sea’ of cells having the opposite color. This initial condition is in the perfect consistence with the rule. One has to keep in mind that both the rule and initial condition are equally important in order to get an effective, correct, and fast solution.
Created by
Mathematica
(April 20, 2004)
