A Poisson allocation of optimal tail

The allocation problem for a d-dimensional Poisson point process is to find a way to partition the space to parts of equal size, and to assign the parts to the configuration points in a measurable, .deterministic. (equivariant) way. The goal is to make the diameter R of the part assigned to a configuration point have fast decay. We present an algorithm for d.3 that achieves an O(exp(.cRd)) tail, which is optimal up to c. This improves the best previously known allocation rule, the gravitational allocation, which has an exp(.R1+o(1)) tail. The construction is based on the Ajtai.Komlós.Tusnády algorithm and uses the Gale.Shapley.Hoffman.Holroyd.Peres stable marriage scheme (as applied to allocation problems).