Such a partition could be achieved in many possible ways, but the one illustrated is a "canonical" choice. Informally, it is constructed as follows. Each centre simultaneously starts growing a circle, all at the same speed. A centre claims all territory encountered by its circle, unless another centre has claimed it earlier, and until the centre reaches its "quota" (the area of the square divided by the number of centres). (Opposite sides of the square are identified, to form a torus). Without the "quota" restriction, the resulting territories would be precisely the Voronoi cells, in which each "site" (location in the square) is allocated to the closest centre.
It is possible to extend the above procedure to the infinite plane (or to space in any number of dimensions). The analogue of uniformly distributed centres is called a Poisson process. If the quota equals 1 unit of area, and the intensity of the process (the average number of centres per unit area) equals 1, then every centre will be satisfied, and all space will be claimed. (Surprisingly, the same is not true if we start with an arbitrary set of centres of "intensity" 1 - if the centres form a regular grid with a single centre missing, then some space will not be claimed in any territory).
The idea of stability as above was introduced by Gale and Shapley in the context of finite problems involving married couples and college admissions. Gale and Shapley introduced a celebrated algorithm (involving iterated proposals and rejections) for constructing stable marriages. The algorithm may be adapted to our setting and proves the existence of a stable partition. Stable marriage problems do not in general have unique solutions, but in our case the preferences of sites and centres are "consistent", both being based on distance; it turns out that this guarantees uniqueness.
The critical case differs qualitatively from the subcritical and supercritical cases in more respects than just absence of unclaimed sites and unsated centres. Roughly, the critical model looks "busier" and possesses "long-range order". One way to formalize these ideas is to consider the random variable X defined as the distance from the origin to the centre whose territory contains the origin (we take X=∞ if the origin is unclaimed). We expect X to be largest in the critical case. Indeed, X has (at least) power-law tails in the critical case, and exponential tails (on the event that it is finite) in the non-critical cases. Known information about the critical case varies with dimension, as follows.
Critical case α=1 | ||
---|---|---|
Dimension | Lower bound | Upper bound |
1 | E(X^{1/2})=∞ | E(X^{1/2-ε}) < ∞ |
2 | E(X)=∞ | E(X^{0.496}) < ∞ |
d>=3 | E(X^{d})=∞ | E(X^{s}) < ∞, some s(d)>0 |
Subcritical case α < 1 and Supercritical case α > 1 | ||
---|---|---|
Dimension | Lower bound | Upper bound |
d>=1 | E(exp CX^{d}; X < ∞)=∞ | E(exp cX^{d}; X < ∞) < ∞ |
C. Hoffman, A. E. Holroyd, and Y. Peres. Tail bounds for the stable marriage of Poisson and Lebesgue. Canad. J. Math., 61(6):1279-1299, 2009. [ PS | PDF ] | |
C. Hoffman, A. E. Holroyd, and Y. Peres. A stable marriage of Poisson and Lebesgue. Ann. Probab., 34(4):1241-1272, 2006. [ PS | PDF ] | |
A. E. Holroyd, R. Pemantle, Y. Peres, and O. Schramm. Poisson matching. Ann. Inst. Henri Poincaré Probab. Stat., 45(1):266-287, 2009. [ PS | PDF ] | |
D. Gale & L. Shapley. College admissions and stability of marriage. Amer. Math. Monthly, 69(1):9-15, 1962. |