Fast Colouring of Square Tiled Planes Using Cellular Automata
Jiri Kroc
Four cellular automata rules performing two-colouring of square tiled planes are proposed – where those deterministic, self-organizing local rules ensure that no two squares having the same colour could touch each other by their common edge. The speed of the first rule could be lowered by creation of a number of anti-phase separation borders – appearing between two neighbouring regions with mutually shifted colouring – which could be protected by use of a seed in the uniform initial colouring. In the second, two time-step rule – derived from the fist one under assumption of symmetry, it is proven that a square lattice of an arbitrary size – possibly infinite – could be coloured within only two time steps. Finally, two self-organizing rules containing no information about cell positions could achieve maximal speed equal to one half of the maximal size of a rectangular lattice.