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

Question

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.

Answer 1

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.