Distance Transforms

Cellular Automata on Directed Acyclic Networks

Richard Scott

CDx Laboratories

Distance transforms can be defined as cellular automata on directed acylic networks on a grid. They are useful for modeling patterns where growth occurs along a front that sweeps across an area, leaving a fixed pattern behind. Examples include the time evolution of 1D cellular automata, and more general cases where the network connections and shape of the front are generated by the rule. An efficient algorithm for distance transforms runs in O(n logn) time where n is the number of grid points, which compares to worst case O(n-cubed) runtime when using a standard 2D cellular automata implementation. Please see my forum post on the subject where I investigated the kinds of patterns generated by some of these rules.

[presentation materials]