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.

Discrete Voronoi diagrams image 1

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

Discrete Voronoi diagrams image 2


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