1
$\begingroup$

Maximal Poisson disk sampling of radius r, applied to a finite planar region, is defined by successively choosing sample points uniformly randomly from the part of the region that is not within distance r from any previously chosen sample point, until no more choices are possible.

As the size of the original region goes to infinity (keeping some constant not-too-weird shape, e.g. a square), the expected density (that is, number of sample points per unit area) produced by maximal Poisson disk sampling of radius 1 approaches a constant. What is that constant?

Conversely, given a target density, what value of r will produce samplings whose expected density is equal to the target? (As the region size approaches infinity, of course.)

I don't see any mention of this in the standard algorithmic references by Cook, Mitchell, Dunbar/Humphries, or Bridson.

UPDATE 2016/05/13: @j.c. pointed out in comment that this is the same problem referred to in previous question Packing density of randomly deposited circles on a plane, aka "Random Sequential Addition" or "Random Sequential Adsorption". The reference given in j.c.'s accepted answer gives an experimentally found estimate "fraction of space filled in the jammed state is around θJθJ=0.5472±0.002". That says the constant I'm looking for is approximately 0.5472*4/$\pi$=0.6967, which is believable.

I can get a bit better estimate by implementing the state-of-the-art algorithm described in Eurographics 2012, Ebeida/Mitchell/Patney/Davidson/Owens "A Simple Algorithm for Maximal Poisson-Disk Sampling in High Dimensions" and running it on a 10000x10000 square region, with toriodal boundaries to prevent edge artifacts. The number of points obtained on five different runs were:

69655186
69654635
69657327
69652623
69652892

which says the point density constant is roughly 0.6965[45] ± .00002.

I'm wondering if there is a formula, or at least an algorithm that converges faster than these experimental results, for computing this number.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.