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

  • $\begingroup$ 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? $\endgroup$ – OmG May 27 at 16:53
  • $\begingroup$ 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? $\endgroup$ – tch May 27 at 16:56
  • $\begingroup$ No. You just need to check using the radius, not check all cell of the grid one by one. $\endgroup$ – OmG May 27 at 17:19
  • $\begingroup$ But the number of cells to check grows with the dimension. $\endgroup$ – tch May 27 at 17:22
  • $\begingroup$ It does not matter here! You just check the adjacency by the radius! So, the number of cells does not matter here. $\endgroup$ – OmG May 27 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.