# Tetris-like falling sticky disks

Suppose unit-radius disks fall vertically from $y=+\infty$, one by one, and create a random jumble of disks above the $x$-axis. When a falling disk hits another, it stops and sticks there. Otherwise, if the disk center reaches $y=0$, the disk stops with its center resting on the $x$-axis. Here is an example of 1000 disks falling at uniformly random $x$-locations within $[-50,50]$:

There are many questions one could ask about this (to me) beautiful and intriguing structure (e.g., about its contact graph), but to be specific, let me concentrate on one quantity: the maximum height $h_{\max}$ as a function of the number of disks $n$ and the $x$-range $R$. (In the above example, $R=100$ and $h_{\max}=94.9$.) It appears that $h_{\max}$ grows linearly, with $h_{\max} \approx n \frac{10}{R}$. Here is plot, where each point is an average of ten trials:

Two questions:

Q1. Is there a simple explanation of the growth of $h_{\max}$?

Q2. Has this process, or something close to it, been studied before?

Ultimately I am interested in determining packing densities of randomly jostled shapes, as explored in the earlier MO question "Average degree of contact graph for balls in a box." Sticky disks are a very simple model along these lines.

-
This reminds me of a picture I saw in the pop-science book Nexus, by Mark Buchanan (page 104), of an analogous process "diffusion-limited aggregation". Probably you are already aware of this: en.wikipedia.org/wiki/Diffusion-limited_aggregation. –  R Hahn Jul 4 '12 at 14:41
Do you mean to write "with slope nearly R/n"? Isn't n the variable on the x-axis? –  Paul Tupper Jul 4 '12 at 15:12
@Paul: Thanks, I rephrased the empirical claim. –  Joseph O'Rourke Jul 4 '12 at 15:39
I wonder: Can it be a coincidence that the image I posted above looks not dissimilar to bubbles rising in a liquid? images.colourbox.com/thumb_COLOURBOX1718473.jpg –  Joseph O'Rourke Jul 5 '12 at 0:08
Joseph: it looks like some kind of algae to me. –  Zsbán Ambrus Jul 5 '12 at 21:17

A discrete space version of your picture (with squares instead of circles) has been studied quite a bit, known as Ballistic Deposition. Here is a video of the process in action:

This process is believed to be in the KPZ Universality class, so that the scaling limit of the height function can be described by the Airy Process with $t^{1/3},t^{2/3}$ scaling parameters.

Here is a short introduction to the theory:

KPZ Universality Class

-
@Jeremy: Thanks for the key term "ballistic deposition," and for the neat video! –  Joseph O'Rourke Jul 4 '12 at 16:06
This must be what a cross section of Trantor looks like, en.wikipedia.org/wiki/Trantor. –  Lee Mosher Jul 4 '12 at 18:06

Diffusion-limited aggregation is different in that you consider ballistic rather than diffusive motion: randomness enters only through x-coordinates of the falling disks.

Have a look at the paper "Ballistic deposition patterns beneath a growing KPZ interface" (http://arxiv.org/abs/1006.4576; I happen to be one of the authors, and will ask my coauthors who are more versed in statistical physics to join the discussion). In particular, it contains some references to the existing literature on ballistic random growth.

People are usually interested in fluctuations of the upper envelope of the growing cluster, because for many such models it falls into the KPZ universality class'' (meaning that upon a proper rescaling its continuous limit converges to a kind of Airy process). In particular the behavior of $h_{\mathrm{max}}$ is a superposition of two phenomena: the obviously linear scaling of the mean height and the scatter of local heights around that mean, which is described by the Tracy-Widom law.

-
@ansobol: Thanks for the reference to your paper, and other useful information. What struck me was that the growth of $h_\max$ is so simple, apparently $\frac{10}{R}$. It is even more striking knowing that it is a superposition of two phenomena! –  Joseph O'Rourke Jul 4 '12 at 17:59

The density of a randomly growing heap is known, but it is model-dependent and non-universal. The linear dependence of the height on number of deposited blocks is evident, however the coefficient in front of this dependence is again model-dependent. The growth can be viewed as a special sequential matrix multiplication as described in http://arxiv.org/abs/1110.3524/ leading to dynamics of 1D Toda chain. One can play with different versions of this model, for example, supposing that there is only left-hand interaction. The corresponding profile will look different, however the fluctuations will be again of KPZ-type.

-
@Nechaev: Thanks for your knowledgeable reply! When you say, "The linear dependence of the height on number of deposited blocks is evident," do you mean it is evident from my plot, or it is theoretically obvious? For I am curious if there is a simple explanation of this (to me) remarkable linearity. –  Joseph O'Rourke Jul 5 '12 at 0:10
Dear Joseph: the height is necessarily bounded between $2\sqrt{3}n/R$ (maximum density) and $2n$ (a single stack), so as long as you view the word "linear" in a suitably asymptotic sense, it is theoretically clear. –  S. Carnahan Jul 5 '12 at 4:05
Nice, Scott---Thanks! –  Joseph O'Rourke Jul 5 '12 at 12:41
Usually the convergence of height divided by time can be obtained from such bounds and a sub-additivity argument. Here, stop after $n_0$ balls, and look until the $n$th one is added: the last land on top of the first $n_0$, so they add less height than if they landed on a flat surface, hence in expectation $h(n) \leq h(n_0) + h(n-n_0)$ so $h(n)/n$ has to converge. –  Vincent Beffara Jul 6 '12 at 12:00

That the growth is asymptotically linear is clear. But if you keep the width $2R$ of the strip (over which the centers are chosen uniformly) fixed, then the growth speed $c_R$ is not strictly proportional to $R^{-1}$. This is clear when thinking to the small width case: if $R<1$, then there is only one branch in the tree because two consecutive disks always touch. If $d$ is the distance between their centers, then they will arrange with a height gap equal to $\sqrt{4-d^2}$. Because the distribution of $d$ has density $$\frac{2R-d}{2R^2},$$ we find that the growth average speed $$\frac1n\sum_1^nd_j$$ tends to the expectation of $\sqrt{4-d^2}$: $$c_R=\int_0^{2R}\sqrt{4-x^2}\frac{2R-x}{2R^2}dx.$$ Calculus gives $$c_R=\frac2R\sin^{-1}R+2\sqrt{1-R^2}+\frac4{3R^2}\left((1-R^2)^{3/2}-1\right).$$ As expected, $c_R\rightarrow2$ as $R\rightarrow0$. On the other hand, $c_1=\pi-\frac43$.

Presumably, the OP is interested with $\gamma=\lim_{R\rightarrow+\infty}Rc_R$.

-

Regarding the question

Has this process, or something close to it, been studied before?

I was recently made aware of an intriguing approach of Bob Macpherson and his post-doc Ben Schweinhart at IAS for investigating Brownian trees via computational topology in this pre-print. Since the investigation is topological, it will not yield answers to your question about maximum height, but it does capture other interesting global statistics.

The central idea is to let a diffusion-limited aggregation process run for a while and generate a configuration similar to that of your picture, but lacking any loops whatsoever. Essentially, each time a disc falling from infinity creates a cycle, it is discarded. However, this discarding step is not necessary for subsequent analysis and so would also apply to your (considerably loopier) situation.

In any case, once the process has run its course and generated a space consisting of the union of balls, you start growing the radii of these balls (allowing overlap of course). As you increase these radii, the homology of the space changes: some loops form, others get filled in and so forth. It is possible to unambiguously associate a (birth, death) interval to each such loop via the theory of persistent homology.

-
As far as I understand there are no cycles in the picture from the original post (with probability 1). This as the values on the $x$-axis for which adding a disk would form a cycle is a finite discrete set, and hence a null set. –  Koen S Jul 5 '12 at 12:55
On the other hand, if you just look at the picture, there are tons of cycles... –  Vidit Nanda Jul 5 '12 at 14:31
I'd suspect if you zoom in enough they aren't connected anymore. –  Koen S Jul 5 '12 at 17:42
I don't think so: can you prove that only finitely many x-values create cycles? This does not seem obvious at all. –  Vidit Nanda Jul 5 '12 at 20:18
@Vel: Either I don't understand your last comment, or I don't understand the OP's question. You can only form a loop if a falling disk touches two disks simultaneously, and for any pair of disks, there is at most one $x$-value for which this is the case. Am I missing something? –  Tom De Medts Sep 13 '12 at 12:57

the height is given by h=2*(Sum Yi)/n , where n the particles, Yi the y coordinate of each particle. Can you give me the source code please?

-