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.
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.