Random placement of euclidean points with constrained inter-point distances in a fixed area

Question

I'd like to place as many random points as possible in a 2D square $S=[0,1]x[0,1]$ such that the euclidean distance $d$ between any two points $d$ is greater than a given value $b$ (b is small). I'm interested in an iterative construction algorithm that successively limits the remaining space where points can be placed. In such a case, I'm curious how to efficiently characterize the available space and how to check the stopping criteria "until no more points can be placed". Any help would be greatly appreciated.

Answer 1

This is called Poisson disk sampling, and there are a lot of papers on the subject. Here are a few:

• D Dunbar, G Humphreys (2006). A spatial data structure for fast Poisson-disk sample generation.
• L. Wei (2008). Parallel Poisson disk sampling.
• R. Bridson (2007). Fast Poisson disk sampling in arbitrary dimensions.
• M. Ebeida et al. (2011). Efficient maximal Poisson-disk sampling

The last one appears to be what you what.