Tail Bounds for the Stable Marriage of Poisson and Lebesgue

Abstract

Abstract Let 𝚵 be a discrete set in ℝ d . Call the elements of 𝚵 centers . The well-known Voronoi tessellation partitions ℝ d into polyhedral regions (of varying volumes) by allocating each site of ℝ d to the closest center. Here we study allocations of ℝ d to 𝚵 in which each center attempts to claima region of equal volume α. We focus on the case where 𝚵 arises from a Poisson process of unit intensity. In an earlier paper by the authors it was proved that there is a unique allocation which is stable in the sense of the Gale–Shapley marriage problem. We study the distance X from a typical site to its allocated center in the stable allocation. The model exhibits a phase transition in the appetite α. In the critical case α = 1 we prove a power law upper bound on X in dimension d = 1. (Power law lower bounds were proved earlier for all d ). In the non-critical cases α < 1 and α > 1 we prove exponential upper bounds on X .

Locations

• Canadian Journal of Mathematics - View - PDF
• arXiv (Cornell University) - View