# Is Poisson Disk Sampling an alternative to crude Monte Carlo and QMC?

I recently stumbled over Poisson Disk Sampling (here and the meditative version). I wonder if it is an alternative to crude or quasi Monte Carlo for very high dimensional integrals. It is not mentioned in Glasserman's Monte Carlo Methods so I suspect there is some draw-back.

## Questions

1. What is known about convergence rates when using Poisson Disk sampling for high dimensional cubature (d>100)?
2. How efficient is the creation of Poisson Disk Samples for high dimensional domains?
3. Is it an alternative to Quasi Monte Carlo methods such as Sobol or Halton sequences? If not, why not?
• MC sits on top of a set of numbers. If they are random, we have montecarlo. If you use a grid, then it maps to being a quadrature. The problem with grids is that when you project them onto the lower dimensions of the problem, they do not sample the space evenly. When you do this in 2d it is simple to solve, since you can rotate the grid. As you increase the number of dimensions it gets harder. Sobol/halton/other low discrepency sequences go a long way towards solving this. – will Jul 16 '16 at 9:31
• I have to admit I fail to see the connection of your comment with Poisson Disk Sampling. Care to elaborate? – g g Jul 17 '16 at 8:47
• I'm saying that it's not an alternative to montecarlo. It is just another way of sampling an N dimensional space, which should sample the space more evenly. – will Jul 17 '16 at 18:47
• This might be moved to crossvalidated. – Quartz Jul 19 '16 at 13:11

The classical and naïve procedure for generating Poisson Hypersphere samples is by acceptance rejection, which has complexity over $O(N^2)$ and is thus unfeasible for most practical usage with on-the-fly generation. This cost could be improved by space partitioning techniques at low dimensions, but at high ones afaik they become useless again with uniform distributions. Poisson disc sampling is thus not used widely beyond dimension 10, and I fear in general it is not a meaningful method in high dimensions because of geometric issues, which are conveniently bypassed by standard low discrepancy sequences (e.g. the fact that most of the hypercube volume is near the boundary). Another drawback w.r.t. some quasi-MC sequences is that smoothness of the integrand is not exploited and thus convergence can be significantly slower.