Notes

Chapter 7: Mechanisms in Programs and Nature

Section 8: The Problem of Satisfying Constraints


Discrete Voronoi diagrams

The k=3, r=1 cellular automaton

{{0 | 1, n : 0 | 1, 0 | 1} -> n, {_, 0, _} -> 2, {_, n_, _} -> n - 1}

is an example of a system that generates discrete 1D Voronoi diagrams by having regions that grow from every initial black cell, but stop whenever they meet, as shown below.

Analogous behavior can also be obtained in 2D, as shown for a 2D cellular automaton in the pictures below.


From Stephen Wolfram: A New Kind of Science [citation]