Complexity of "Fast Poisson Disk Sampling in Arbitrary Dimensions"

Question

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).

Answer 1

I have just implemented this algorithm, generalized for an arbitrary number of dimensions. You are absolutely correct in your suspicions about the exponential growth with $n$, as far as I see.

Each of these $2 N - 1$ iterations require a lookup in the neighbourhood for each candidate, and the neighbourhood scales up exponentially with the dimension: from a line to a square to a cube, etc. A more accurate implementation can slow this growth by excluding the corners of the hypercube in higher dimensions, since they don't fulfil the distance criteria, but it won't stop the exponential growth.

Increasing the $k$ for the higher dimensions, on the other hand, does not make much sense to me. $k$ are the candidate points to be tested for acceptance, so if you find at least one valid point among them, the algorithm will continue until the entire space is filled. If anything, I think it's easier to find a valid point for a higher-dimensional case, since there are more degrees of freedom.

Also, here's a link to my implementation: https://github.com/diregoblin/poisson_disc_sampling