# Complexity of “Fast Poisson Disk Sampling in Arbitrary Dimensions”

I came across the paper Fast Poisson Disk Sampling in Arbitrary Dimensions which gives an algorithm for generating Poisson disk points in $$\mathbb{R}^n$$. It's claimed that the algorithm is linear time. However, I wonder if this assumes the dimension n is constant.

My understanding of the analysis is that to generate $$N$$ points requires $$2N-1$$ iterations, and each iteration is constant time. I agree with the $$2N-1$$ iterations, but I'm not sure about each iteration being constant time.

In each iteration, they sample a small constant $$k$$ points, and then check whether or not these points are near to any of the previously generated points using a background grid to assist. However, isn't the number of neighboring cells to check exponential in $$n$$? It seems like the runtime of the given algorithm using the background grid should be something like $$k N \exp(n)$$, (or $$kN^2$$ if you just check the other points directly).

Have I misinterpreted the algorithm or the analysis? I get that for a fixed $$N$$ it will be constant (assuming $$k$$ is constant). Is that the standard assumption when saying an algorithm is "linear time"? To me this seems a bit misleading because they mention dimension in the title. If you go to high enough dimension and use the "constant time" algorithm, the constant will be exponential in $$n$$ which means the algorithm is not "fast" in "arbitrary dimensions".

As an afterthought, does it even make sense for $$k$$ to be constant. If you don't increase $$k$$ exponentially with $$n$$ then the "density" (number of points per volume) of the points will go to zero (although this is more of a "modeling" choice than an analysis choice).

• The algorithm just checks the $k$ samples, not all neighbors. So, why do you think the number of neighbors should be multiplied in the complexity? – OmG May 27 at 16:53
• To check if one of the $k$ samples is near to any other point don't you have to check either all adjacent grids blocks, or all previous points? – tch May 27 at 16:56
• No. You just need to check using the radius, not check all cell of the grid one by one. – OmG May 27 at 17:19
• But the number of cells to check grows with the dimension. – tch May 27 at 17:22
• It does not matter here! You just check the adjacency by the radius! So, the number of cells does not matter here. – OmG May 27 at 17:27