# Growing random trees on a lattice $\rightarrow$ Voronoi diagrams

Imagine growing trees from $k$ seeds on a square $n \times n$ region of $\mathbb{Z}^2$. At each step, a unit-length edge $e$ between two points of $\mathbb{Z}^2$ is added. The edge $e$ is chosen randomly among those that have one endpoint touching an existing tree and the other endpoint not touching any tree. Edge $e$ then extends the tree $T$ it touches, maintains $T$ a tree, and does not join to another tree. The process is repeated until no such edges remain. Here is a view of (a portion of) the trees grown from three seeds:

I expected the trees to intertwine and tangle with one another as they grew, but instead they appear to be approximating the Voronoi diagram of the seeds. Here is an example (of which the above is a detail) of $k=10$ trees grown within a $100 \times 100$ square:

I have overlaid the Voronoi diagram of the seeds.

My primary question is:

Q1. Is it known that a tree-growth process like mine approximates the Voronoi diagram in some sense?

Short of this, I would like to correct my faulty intuition:

Q2. Why do the trees not entangle more significantly where they meet?

Finally:

Q3. Are there any results known on the structure of the individual grown trees? For example, their expected height, perhaps as a function of their Voronoi region shape? (Not surprisingly, the tallest tree ($h=110$) above is the mauve one with root $(61,41)$ that encompasses the upper right corner.)

Although the book Percolation has a chapter on "Random Voronoi Percolation," I have not been successful in matching their models to mine closely enough to draw any definite conclusions.

Thanks for any pointers to relevant literature!

-
Spanning forests on $\mathbb Z^2$ are in bijection with domino tilings on $\frac{1}{2}\mathbb Z^2$, so it seems like this can also be transformed into a question about liquid/gaseous regions of the corresponding dimer model. Perhaps the work of Kenyon-Okounkov is relvant? – Gjergji Zaimi Sep 28 '11 at 11:42
Great question by the way! – Gjergji Zaimi Sep 28 '11 at 11:52
Two questions. 1. Do the unit length edges you add have to be horizontal or vertical? 2. How is the first edge added for a given seed? Should the seed be one of its endpoints or should it just lie on it somewhere? – Vinayak Pathak Sep 28 '11 at 12:01
Might I suggest a more focused experiment which might help pin down one "universality class"? Go with just two seeds placed vertically from each other (though different "slopes" are also interesting) and study the width of the interface between them as a function of the distance between them. I will boldly guess that the width grows as a power law with an interesting exponent, which might give a clue as to what kind of random curve the interface is limiting onto e.g. a percolation interface or SLE, diffusion front / gradient percolation type thing, or something else entirely. – j.c. Sep 28 '11 at 14:07
What a lovely question, the liquid/gaseous regions work does seem relevant. A quick thought, given the way that the tress grow the taxi driver metric on \mathbb{Z}^2 is perhaps more appropriate for the Voronoi tiling. With this metric the probability of a tree reaching a certain point should be a function of distance. This might give you a window into what is happening at the boundary. As another commentator mentioned looking at how the trees change with distance and just 2 seeds might also help. – Edmund Harriss Sep 28 '11 at 14:50

Update:

I think your model for growth has been studied before and goes by the name of the Eden growth model (See section 4 of the (linked) original paper by Murray Eden). It seems what is usually studied is a "site addition" model, whereas your model is a "bond addition" model, but I bet the main results will be the same. I haven't managed to find any recent reviews focusing just on the Eden model yet (and the Wikipedia page is sadly very sparse), but I found a description of it in the first pages of this book chapter of Jean-François Gouyet's "Physics and Fractal Structures".

Famously, the interface of the Eden model was the motivation of Kardar, Parisi and Zhang when they defined the universality class now known as KPZ. Here's a nice review of the KPZ universality class by Ivan Corwin.

Thus a lot is (conjecturally) known about this -- in particular, the size of the fluctuations at the perimeter of a single tree with $N$ bonds should scale as $N^{1/6}$ (fluctuations go as radius$^{1/3}$, and I am pretty sure the radius goes like $N^{1/2}$). Because of this site versus bond addition discrepancy, I haven't found anything about colliding Eden clusters, but I think these ideas can justify that you do get Voronoi cells. I would be delighted to hear criticism or details from an expert!

I don't have anything rigorous to say yet, but some post-facto intuition for Q2 is as follows.

Consider the case of a single seed. I'll tell a story about why the growth from a single seed ought to look more or less like a disk with a wiggly edge, rather than something with a lot of branchy and spread-out fingers (like something one gets out of diffusion-limited aggregation, for instance). If you buy my story, then it should be clearer why there isn't that much "entanglement" at the interfaces between two such growing bodies.

At a given time step $i$, we have a tree $T_i$; let the set of edges that connect $T_i$ to $\mathbb{Z}^2\setminus T_i$ be $G_i$. Then we may form $T_{i+1}$ by choosing uniformly an edge in $G_i$ and adding it to $T_i$. So far, this is just your process in different terms. Here comes some handwaving. Any "protrusions" on $T_i$ will not get too long, because to grow a subset of $T_i$ which sticks out a significant distance from the rest of $T_i$, we'd have to had chosen edges near the "tip" of this protrusion repeatedly. But of course the tip of a long protrusion has a small perimeter compared to the sides of the protrusion, and thus it's much more likely that added edges will smooth out any such features instead of extending them.

Why does this end up with something disk-like? Your process is basically one where you add a "protrusion" to the tree centered somewhere uniformly random on the "boundary". Thus consider the following "off-lattice" version of your process. Let $T_0$ be a disk of radius 1 centered at the origin. $T_i$ is the union of $T_{i-1}$ with a disk centered at a point $p_i$ chosen uniformly from the boundary of $T_{i-1}$. I hope you can see that this is a stochastic version of normal evolution of the boundary. And as is well-known to doodlers, normal evolution tends towards to circular disks, so "intuitively" a stochastic version will tend to a wiggly disk. (One complication here is that your process isn't allowed to form loops in the tree, whereas the continuum version I have in mind does).

-
OK, I was very sloppy about the effect of the lattice in my last paragraph. Ori Gurel-Gurevich's answer has convinced me that one needs to be careful about such things, but I still find my analogy to normal evolution (with the Euclidean metric rather than anything else) plausible. – j.c. Sep 28 '11 at 16:51
@jc: Your argument that explains why protrusions are rare is intuitively convincing to me! When I get a window of free time, I will explore experimentally. – Joseph O'Rourke Sep 28 '11 at 17:24
I wonder if this can be overcome by changing the probability function. An edge whose new endpoint gave lots of new options, or could be chosen in preference to an edge that filled a gap. This should give the trees a more branchlike and less blob-like structure and so lead to a lot more entangling. Reading between the lines that seems to be what Joseph might like! – Edmund Harriss Sep 28 '11 at 18:05
@Edmund Harriss: That's an interesting line of thought too. You might want to look into Diffusion Limited Aggregation (DLA) processes which form very branchy trees; roughly speaking the probability of adding a site to a DLA process is weighted by the probability of hitting the site with a random walk coming in from infinity, thus the tips end up preferred in such models. – j.c. Sep 29 '11 at 0:42
Though DLA is well studied, it seems in the usual version with multiple seed sites that is considered, the clusters have a possibility of being connected by a site and then merging, and so I haven't found any works that study how the plane ends up being partitioned into different regions. See e.g. link.aps.org/doi/10.1103/PhysRevB.28.5632 – j.c. Sep 29 '11 at 0:45

Q1: It is unlikely that you get the Voronoi diagram. Take a look at "Richardson's growth model" which is closely related (it is your model without the trees). The limit shape there is not a disc, meaning that the model is not rotationally symmetric in the limit, so it's not Voronoi cells.

http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aop/1176994460

-
@Ori: Thanks! I did not know of Richardson's model. It does approach a convex limiting shape asymptotically, so maybe my process approaches a Voronoi diagram, but under a metric different from the Eulidean metric (as suggested by Edmund). – Joseph O'Rourke Sep 28 '11 at 16:00
I do not quite see how to map Joseph O'Rourke's model to Richardson's growth model. In Joseph O'Rourke's model, one site is added at each time, whereas in Richardson's growth model, many sites are added at each time, depending on the value of $p$. I guess if one lets $p$ decrease as the perimeter of the object grows, you might get a version of Richardson's growth model which is closer to Joseph O'Rourke's model. Is there anything known for that case? – j.c. Sep 28 '11 at 16:47
@jc: the only global effect here is the overall rate in which sites/edges are added. In other words, in the Richardson model, the next edge to be added is distributed uniformly among the edges connecting infected and non-infected sites. – Ori Gurel-Gurevich Sep 29 '11 at 6:28
This survey page of Durrett's math.cornell.edu/~durrett/survey/survc1.html seems to suggest that this was proven in Richardson's paper, but in fact the question of whether the limit shape is a round disk is open problem (6) of Richardson's paper. The main theorem of Richardson's as applied to this particular model seems to be that the limit shape exists and is convex but I can't see how to rule out that it's a round disk. – j.c. Sep 29 '11 at 12:00
@jc: Frankly, I remember the result (that it's not a disc), but not where is it from, so I could be mistaken. – Ori Gurel-Gurevich Sep 30 '11 at 5:35

Let me just quickly post one additional figure, a nod in the direction suggested by jc and Edmund. The left image shows the trees for two sites. The right image is a 3D depiction of the same trees, but this time with each node raised in $z$ by its tree height (with the white dots marking the two roots, at heights 47 and 55).

(I don't have time at the moment to make a more thorough analysis.)

Continuing to use this "answer" to supplement the comments, here are four random trees grown from one seed, each consisting of about 5000 edges:

And here is zoomed detail from the lower right of the brown tree above:

-
Lovely! It's interesting in light of the last sentence of my post that there do indeed seem to be a few small pockets of "uninfected" sites disconnected from the outside in the single trees. Is it feasible to generate many trees with $N$ edges and then to "average" them to see the mean shape? I still have my money on a circular disk of size $N^{1/2}$. – j.c. Sep 29 '11 at 0:16
There are obvious simple ways, like, sample the radius at N different evenly-spaced angles and average the radius. – Will Sawin Sep 29 '11 at 5:04
But wouldn't one expect those pockets to be filled by that same color later on, thanks to the untouched points inside them which still allow to go on ? – Thomas Sauvaget Sep 29 '11 at 14:45
@Thomas: Yes, definitely. My process does not need access "from the outside." You are correct. I only highlighted the pockets because they relate to a point of jc's. Also, I just love these tree images as aesthetic objects! :-) – Joseph O'Rourke Sep 29 '11 at 14:51
Joseph: I suggest trying this with the triangular lattice and comparing the results for (essentially) the same initial seeds. See my comments to Ori above. – Steve Huntsman Sep 30 '11 at 23:26