Mitchell, Scott A.Campen, MarcelSpagnuolo, Michela2022-06-272022-06-2720221467-8659https://doi.org/10.1111/cgf.14606https://diglib.eg.org:443/handle/10.1111/cgf14606We 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.CCS Concepts: Mathematics of computing --> Distribution functions; Computing methodologies --> Rendering; Theory of computation --> Randomness, geometry and discrete structuresMathematics of computingDistribution functionsComputing methodologiesRenderingTheory of computationRandomnessgeometry and discrete structures10.1111/cgf.14606101-11111 pages