April 14th, 2012

beartato phd

(no subject)

Been reading a bit about the Poisson disk distribution, which is easy enough to describe, but tricky to sample from. What it is is: you let uniformly randomly distributed points arrive, and you accept the ones that are not within r distance of any previously accepted point. The linked article describes one way to do this, but evidently the standard problem with this distribution in principle is you don't know when to stop generating points. The theoretical distribution is: keep generating points until no more can be.

I think probably you could do something with quadtrees, for if some circles don't cover all the grid cells at first:
circles
you could keep making the grid smaller until either they do:
circles2
or else you find a point in a not-necessarily covered square that actually does have some acceptable space.

And I think you can probably speed up the point sampling by doing it more locally, treating the arrivals process as a 3d poisson process in spacetime, and taking longer, skinnier, more timey-wimey bits
sampling
that nonetheless have the same volume, and taking a geometric distribution to determine how many arrivals are in that chunk, and the uniform distribution over where they are in the chunk.