# Is there an algorithm for distributing an unknown number of objects so that the overall distribution is as evenly as possible?

Today I was putting pieces of salami onto a pizza. Because my son had been nibbling them, I did not know how many there were. I therefore did not know how best to distribute the pieces so that they were evenly distributed. This got me wondering...

If there is only one item, then I think that the best place to put it is in the centre.

If there are 25 items, then I would have thought that placing the items uniformly in a 5 by 5 grid would be the most uniform (it was a square pizza).

If there are $n$ items, then there must be an arrangements of those items that leads to the "most uniform" distribution. Of course we need to define what is meant by the "most uniform" distribution...

If, however, we don't know $n$, what should my strategy be?

I know that this will depend on the probability distribution for $n$, so I propose that $n$ has a geometric distribution:

We know that $n$ is at least $1$. After placing the first item, there is a probability $p$ that we have a second to place and a probability $1-p$ that there are no more. At each stage, let there be a probability $p$ that we have another item to place and a probability $1-p$ that there are no more.

I started assuming that the distribution is to be over a square. You can change that to a circular pizza if it's easier.

In looking into this I have found another question about distributing points over a sphere Is the Fibonacci lattice the very best way to evenly distribute N points on a sphere? So far it seems that it is the best?

My question would be different to that in that I don't want the number of points to be determined before I start placing them.

My gut feeling is that this is like the problem of deciding when to park your car in an available space and when to continue on towards your destination in the hope that you will find another space closer to your destination.

• A good decision rule for this case, when you do not know $n$, is to independently place each object randomly and uniformly distributed over the area of interest. Suppose the total area is $A$. Then the total density is $d=n/A$ objects per unit area, and this random placement ensures that in any subregion of size $s \leq A$, the expected number of objects is exactly $d s$. So the localized density is uniform over the region of interest. So: just randomly throw those salamis anywhere! – Michael Oct 15 '16 at 22:01
• This relates to a fundamental information theory result: It is difficult to place $n$ points in a multi-dimensional ball to maximize the minimum distance between two points, even if we know $n$ in advance. Claude Shannon said that it is a good idea to randomly place the points, and this gives rise to the optimal capacity theorem for point-to-point communication over a noisy channel with a fixed bandwidth! (The "points" are Fourier series coefficients for a signal transmitted over a bandwidth-limited channel). His argument is a so-called "random coding argument." – Michael Oct 15 '16 at 22:07
• @Michael Yes, this is a good rule, and may well be the best rule. But the moment we place the first piece, we change the geometry of the space. It feels wrong to place the second anywhere near the first, because if we have to stop after the second, we will have a poor distribution. Even if we get to stop after the third or fourth, we might still be wondering why the first two are so close together. Should there be some kind of "exclusion zone" around the first item? – tomi Oct 15 '16 at 22:08
• @Michael Is it any easier to consider points on a straight line? – tomi Oct 15 '16 at 22:09
• For a straight line you could also do random point-throwing, but it seems more reasonable to do a deterministic positioning in this case: Chop a max-size interval in two every step! I think this ensures your min-distance is off by at most a factor of 2 in comparison to a completely uniform placement of length $1/(n+1)$ (which you could only do if you knew $n$ in advance). – Michael Oct 15 '16 at 22:12

There is a notion of the discrepancy of a finite set of points in $[0,1)^n$, which measures the deviation of the point set from a uniform distribution. What follows is taken from Kuipers and Niederreiter, Uniform Distribution of Sequences, which I recommend highly.

Let $x_1,\dots,x_N$ be a finite sequence in $[0,1)^k$. The discrepancy $D_N$ is defined by $$D_N=D_N(x_1,\dots,x_N)=\sup_J\left|{A(J;N)\over N}-\lambda(J)\right|$$ where $J$ runs through all subintervals of $[0,1)^k$ of the form $$J=\{\,(u_1,\dots,u_k)\in[0,1)^k:\alpha_i\le u_i<\beta_i\rm{\ for\ }1\le i\le k\,\}$$ Here, $A(J,N)$ is the number of terms of the sequence lying in the subinterval $J$, and $\lambda(J)$ is the Lebesgue measure of $J$ (which is just $\prod_i(\beta_i-\alpha_i)$). So, we're subtracting the proportion of points that "should" be in $J$ from the proportion actually in $J$, and then looking over all $J$ to find the supremum of this difference.

Given a point set $\omega$ of unknown length, we let $D_N(\omega)$ be the discrepancy of the first $N$ terms of the sequence. What you want is a sequence $\omega$ that keeps $D_N(\omega)$ small for all $N$.

There are theorems that say that you can't keep it too small. Theorem 2.2 says for any infinite sequence $\omega$, there are infinitely many positive integers $N$ such that $$ND_N^*(\omega)>C_k(\log N)^{k/2}$$ where $C_k>0$ is a constant depending only on $k$ (and I should have mentioned that for applications to pizza, $k=2$). Here, $D_N^*$ is a modified version of $D_N$ – see the book for the details.

As for actual sequences that keep the discrepancy small, the book describes the van der Corput sequence, of which it says that no infinite sequence has yet been found that has a uniformly smaller discrepancy. That's in one-dimension, but then in the notes there are discussions of the van der Corput-Halton sequence, and of the Hammersley sequence, which are low discrepancy sequences in higher dimensions. You can probably find lots of information on these sequences by typing "van der Corput-Halton", or "Hammersley sequence", or "low discrepancy sequences" into the internet and seeing what comes back at you.

• That is helpful. Thank you for the van der Corput sequence. – tomi Oct 15 '16 at 23:44
• Is there a straightforward way to calculate $D_N$ for a given sequence? – tomi Oct 18 '16 at 10:07
• As well as keeping $D_N(\omega)$ small, I think I want to keep the expected value of $D_N(\omega)$ small under the distribution of $N$. – tomi Oct 18 '16 at 10:09
• There's a very simple way to calculate $D_N$ (or anyway $D_N^*$) in one dimension. I'm not so sure about higher dimensions, but if it exists, it's in the Kuipers & Niederreiter book. I don't know what you mean by "under the distribution of $N$". If you keep $D_N(\omega)$ small, doesn't that also keep the expected value of $D_N(\omega)$ small? – Gerry Myerson Oct 18 '16 at 12:09
• $$E\left(D(\omega)\right)=\Sigma_{i=1}^{\infty}\left(D_i(\omega)\times P(N=i)\right)$$ – tomi Oct 18 '16 at 13:51