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(ncubed) 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]


