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:

The last one appears to be what you what.

  • $\begingroup$ Yes, I think this is exactly what I was looking for! I didn't even realize it had a technical name: Poisson disk sampling. Thanks, Geoffrey! $\endgroup$
    – Paul
    Aug 27 '12 at 15:09

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.