Intro Soup Recipe Shelf Sink Chef
Take me higher...

Threshold and Monotone Growth

We begin our survey with the most tractable CA growth models, the monotone solidification rules in which an empty cell joins the occupied set iff it sees enough occupied sites around it. More precisely, in Threshold Growth a 0 (empty) to 1 (occupied) transition occurs at x if the neihborhood N of x contains a at least threshold t occupied cells. We will assume that N is symmetric for simplicity, focusing on the range r box neighborhood case, which we denote Br .

Such models are naturally classified according to whether or not they are capable of filling the lattice eventually. Since Threshold Growth is a solidification rule, a final configuration Af of occupied sites exists. Call An supercritical if Af = Z2 starting from some finite A0, subcritical if Af is a proper subset of Z2 for some initial A0 with finite complement, and critical otherwise. For symmetric N one can give a complete classification (see [GG2]).The range r Box rule is supercritical for treshholds up to 2r2+r, and subcritical for thresholds exceeding 2r2+r. The crux of the first assertion is to show that a sufficiently large lattice ball fills the lattice as long as the threshold is appreciably less than half the size of the neighbor set.

To motivate the discussion of asymptotic shape for Threshold Growth, consider our Basic Example : range 1 box, with t = 3. Note that this is the Moore neighborhood rule with highest supercritical threshold. From a suitably large seed A0, say any configuration consisting of 3 continguous cells, An rapidly forms a linearly expanding "lattice octagon," so the shape result (#) of Section 1 holds with L = O = the octagonal region bounded by vertices (0,1/2), (1/3,1/3), and others determined by lattice symmetry. The most straightforward route to Theorem 1 for specific rules is to compute iterates exactly. In our case, starting from the Range 1 diamond seed D, it turns out that the dynamics are recursive. Fig. 1a shows each 6 updates in a new shade of gray. One can write down an explicit formula for An, checking the first few iterates directly and then observing that the "sides" of the lattice octagons advance like boundaries of half-spaces while the "corners" advance with period 2 (horizontal, vertical) and 3 (diagonal; Fig. 1b).

Fig. 1 Iterates of the Basic Example and detail of a stable corner

Together, these observations show convergence to O by induction. Next, starting from any finite A0 which covers D, by monotonicity A0 is sandwiched between iterates from D which differ by a fixed number of time steps, and (#) follows.

With larger neighborhoods and thresholds, exact recursion becomes increasingly difficult, so an alternate method is needed in order to establish the Shape Theorem for Threshold Growth in full generality. An approach familiar to statistical physicists ([KrSp], [Wu]) is based on half-space propagation. The idea is that any expanding droplet should become locally flat as it grows, and so its displacement in direction v is determined by the advance of a half-space Hu = { < x , u > < 0 }, where u is the outward normal unit vector to the boundary of L in direction v. After some convex analysis [GG1], the recipe is essentially as follows. By translation invariance, each iterate of the dynamics displaces Hu some fixed amount w(v) known as the speed. From this computable data, form the region K of the plane with extent w -1. Then the asymptotic shape L is given by K*, the polar transform of K.

  Back  

  Next

Gravner and Griffeath

Take me higher...
Intro Soup Recipe Shelf Sink Chef