A Poisson allocation of optimal tail

Abstract

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\ge 3$ that achieves an $O(\exp (-c{R}^d))$ tail, which is optimal up to $c$. This improves the best previously known allocation rule, the gravitational allocation, which has an $\exp (-R^{1+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).

Published at http://dx.doi.org/10.1214/15-AOP1001 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (4)

• Extra heads and invariant allocations
• A stable marriage of Poisson and Lebesgue
• Optimal transport from Lebesgue to Poisson
• Connected allocation to Poisson points in R^2

Cited by in corpus (1)

• Poisson allocations with bounded connected cells