THEORETICAL GUARANTEES FOR POISSON DISK SAMPLING USING PAIR CORRELATION FUNCTION

In this paper, we study the problem of generating uniform random point samples on a domain of d-dimensional space based on a minimum distance criterion between point samples (Poisson-disk sampling or PDS). First, we formally define PDS via the pair correlation function (PCF) to quantitatively evaluate properties of the sampling process. Surprisingly, none of the existing PDS techniques satisfy both uniformity and minimum distance criterion, simultaneously. These approaches typically create an approximate PDS with high regularity, and inherently present high risk for sample aliasing. Our new formulation based on PCF introduces a new approach to evaluate PDS properties which leads to theoretical bounds on the size of a PDS in arbitrary dimensions as well as a faster algorithm to create better quality samplings than the current PDS approaches.