Random Recipe

The Cook Book

Recipe for the week of October 16 - 22

Dynamic Formation of Poisson-Voronoi Tiles

Here's an example of self-organization featured in my lecture at the 1995 Midwest Probability Colloquium this week. More than a half century ago, Johnson and Mehl proposed various dynamic models for crystal formation that combine Poisson-distributed nucleation centers, linear isotropic growth of crystals, and "standoff" interaction at the boundary. Through computer experimentation with WinCA, CAM8, and other simulations, we have found large families of CA rules with the same phenomenology, except that the norm for growth is given by the Threshold Growth Shape Theorem (cf. last July 24).

This week's soup depicts one such example. Start by coloring the lattice randomly with 64 colors. At each step, the color k at site x changes to a new color k' if it sees at least 4 sites of color k' within its range 2 Diamond neighborhood for a unique k' ; otherwise there is no change at x. The resulting evolution is sometimes called a multitype threshold voter model. Our graphic shows the state of a 512 by 400 such system (with free boundary) after 100 updates. The model has almost fixated, but not quite. Can you find the last remnants of activity? Another puzzle: notice the small red dot in the middle of the blue cluster at the far lower right. What happened there?

To see this same trajectory earlier in the process of nucleation, look at Time 40. Evidently the final design is some sort of random tiling. In fact one can prove that the tile boundaries, suitably interpreted and rescaled, tend toward a mathematical structure known as a Poisson-Voronoi tessellation as the number of colors grows. In this instance the proper scaling turns out to be (398)^.5 (# colors)^(-1.5). Details will appear in a forthcoming research paper with Janko Gravner.

Take me higher...
Introduction to the PSK PSK Search Recent Additions CA Archive CA Links Feedback Appreciated !