Deterministic Linear Time for Maximal Poisson-Disk Sampling using Chocks without Rejection or Approximation

Abstract

We show how to sample uniformly within the three-sided region bounded by a circle, a radial ray, and a tangent, called a ''chock.'' By dividing a 2D planar rectangle into a background grid, and subtracting Poisson disks from grid squares, we are able to represent the available region for samples exactly using triangles and chocks. Uniform random samples are generated from chock areas precisely without rejection sampling. This provides the first implemented algorithm for precise maximal Poisson-disk sampling in deterministic linear time. We prove O(n.M(b) log b); where n is the number of samples, b is the bits of numerical precision and M is the cost of multiplication. Prior methods have higher time complexity, take expected time, are non-maximal, and/or are not Poisson-disk distributions in the most precise mathematical sense. We fill this theoretical lacuna.