4 ms·

Thanks for the links. Yeah, I'm not too sure that "uniform" is the right term here. I'm happy to be corrected on what the best term is for that specific set of

Thanks for the links. Yeah, I'm not too sure that "uniform" is the right term here. I'm happy to be corrected on what the best term is for that specific set of requirements. It's surprising how hard a time I've had googling this problem. Surely I'm far from the first to wonder about it. I think a mix of AI enshittification, and the ambiguous meanings of "sampling" and "uniform" made it hard to find good material on it.

PaulHoule 2y ago
Sampling points on a disc is a special problem that turns up a lot in practice. One obvious thing to do is just sample points on the square and throw out the ones that aren't in the disc but numericists don't like the throwing away bit because of performance. That Numerical Recipes book [1] has a section on it (has one on disc sampling and those sexy quasirandom numbers), the #1 answer on this StackOverflow page describes an algorithm that I remember from it. https://stats.stackexchange.com/questions/481543/generating-random-points-uniformly-on-a-disk https://stats.stackexchange.com/questions/481543/generating-... [1] I took a class on numerics taught by one of the authors; great book but it's a shame about the software license
- mturmon 2y ago
  > ...numericists don't like the throwing away bit... Although in 2 dimensions (setting of OP), this isn't that bad (you waste a proportion of (1-pi/4), or 21%, of your samples) -- perhaps 21% might be worth worrying about for some applications. Of course, it gets much worse in higher dimensions, because the unit ball is much smaller than the unit cube there.
  - mattkrause 2y ago
    This obviously depends on a million other factors too (implementation, language, architecture, etc) but I've benchmarked this a few times and, at least for naive implementations in 2D/3D, rejection sampling was often faster.
- a_e_k 2y ago
  In graphics, we also often try to avoid any kind of rejection sampling because it wrecks importance sampling.
  - mturmon 2y ago
    Hmm, interesting. Is this still the case if the rejection factor is known explicitly (as it would be here)?
cozzyd 2y ago
Maybe you mean something like regular? I wouldn't call this sampling uniform.

PaulHoule 2y ago

Sampling points on a disc is a special problem that turns up a lot in practice. One obvious thing to do is just sample points on the square and throw out the ones that aren't in the disc but numericists don't like the throwing away bit because of performance. That Numerical Recipes book [1] has a section on it (has one on disc sampling and those sexy quasirandom numbers), the #1 answer on this StackOverflow page describes an algorithm that I remember from it. https://stats.stackexchange.com/questions/481543/generating-random-points-uniformly-on-a-disk https://stats.stackexchange.com/questions/481543/generating-... [1] I took a class on numerics taught by one of the authors; great book but it's a shame about the software license

mturmon 2y ago
> ...numericists don't like the throwing away bit... Although in 2 dimensions (setting of OP), this isn't that bad (you waste a proportion of (1-pi/4), or 21%, of your samples) -- perhaps 21% might be worth worrying about for some applications. Of course, it gets much worse in higher dimensions, because the unit ball is much smaller than the unit cube there.
- mattkrause 2y ago
  This obviously depends on a million other factors too (implementation, language, architecture, etc) but I've benchmarked this a few times and, at least for naive implementations in 2D/3D, rejection sampling was often faster.
a_e_k 2y ago
In graphics, we also often try to avoid any kind of rejection sampling because it wrecks importance sampling.
- mturmon 2y ago
  Hmm, interesting. Is this still the case if the rejection factor is known explicitly (as it would be here)?

cozzyd 2y ago

Maybe you mean something like regular? I wouldn't call this sampling uniform.