MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Thus a lot is (conjecturally) known about this -- in particular, the size of the fluctuations for at the perimeter of a single tree with $N$ bonds should scale as $N^{1/3}$. Not N^{1/6}$(fluctuations go as radius$^{1/3}$, and I am pretty sure what is known the radius goes like$N^{1/2}$). Because of this site versus bond addition discrepancy, I haven't found anything about two colliding Eden clusters, thoughbut 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 Q3Q2 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). 2 Eden, KPZ 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 Eden). It seems people usually have studied the "site addition" case for this, rather than your bond addition, but I bet the main features are the same. I haven't managed to find any good 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 "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 known about this -- in particular, the size of the fluctuations for a single tree should scale as$N^{1/3}$. Not sure what is known about two colliding Eden clusters, though. 1 I don't have anything rigorous to say yet, but some post-facto intuition for Q3 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).