# Finding optimal point distance to get desired number of random points in an area

I have a random point generator which takes a distance $d$ and fills an area with points such that distance between any two points is no less that $d$:

I need to control the number of points in the area, but how to choose $d$? What is needed is just a rough guess since the best $d$ is found using a binary search algorithm.

The point generation is time consuming so the better the initial guess, the faster the heuristic search will be.

Any ideas on how to guess $d$?

## 1 Answer

Assume the points can be reordered in a square grid. Then increasing distance between points will grow the squares of the grid. Therefore the number of points will be inversely proportional to $d^2$.

Since area is known for some units (pixels in my case), we can tell the number of points $n_{max}$ for the distance $d_{min}=1$ pixel, which is simply the number of pixels in the area.

The estimated number of points then becomes

$$n=n_{max}\cdot(\frac{d_{min}}{d})^2=\frac{n_{max}}{d^2}$$

and

$$d=(\frac{n_{max}}{n})^{\frac{1}{2}}$$