3
$\begingroup$

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

$\endgroup$
8
  • $\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, 2019 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$ May 27, 2019 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, 2019 at 17:19
  • $\begingroup$ But the number of cells to check grows with the dimension. $\endgroup$ May 27, 2019 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, 2019 at 17:27

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.