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.


1 Answer 1


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
    Commented Aug 27, 2012 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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