I've seen a number of 2D Poisson disc sampling algorithms online that use a grid to accelerate checking for existing points within the minimum radius [![r][r image]][r link] of a candidate point. For example:
They use a grid of squares of side $\frac{r}{\sqrt2}$, which is the same side length that I intuitively came up with when implementing this myself.
I can see the reason - that is the largest square that cannot contain more than 1 point (assuming the minimum is not attainable - the distance between two points must be strictly greater than $r$).
However, having thought about it further, I adjusted the grid size to $\frac{r}2$ instead. This finer grid means 4 additional squares need to be checked (the 4 corner squares are now within the radius), but the total area covered by the required squares is less, so that on average fewer points will need to go through the Euclidean distance check. The difference can be visualized using the same style as the diagram in the first linked article.
For a candidate new point, existing points must be checked in all squares that are within a radius $r$ of the corners of the candidate's square. Here the two grid sizes are shown side by side, to scale, for the same radius $r$. This shows clearly that a significantly smaller area is being checked. Each square is exactly half the area of the previous approach, and even if the 4 outer corner squares are excluded in the previous approach (left image), this still gives an area $2 \cdot \frac{21}{25} = 1.68$ times larger than in the new approach.
My main question is this: Is this approach still correct, and does it give identical results?
I'm also interested to know whether there is any reason to favor the $\frac{r}{\sqrt2}$ approach. Using $\frac{r}{2}$ seems more efficient in time, which seems worth the cost in space efficiency. Is there anything I'm missing?
Images produced with this jsfiddle (in case I need to edit them later).