3 ms·

I love the halton sequence. Super useful in many situations. I'm surprised Wikipedia describes it as "an example of a quasi-random number". To me, the Halton

by mg 3y ago

I love the halton sequence. Super useful in many situations. I'm surprised Wikipedia describes it as "an example of a quasi-random number". To me, the Halton Sequence answers the question: In a given n-dimensional area, where is the most space left? So if you want to fill an area in an optimal way (each point is placed in the middle of the largest empty area) you can do: 10 I = 0 20 POSITION = HALTON(I) 30 DRAW_A_POINT(POSITION) 40 I++ 50 GOTO 20 This is not only useful for graphical applications. But also to explore a search space for example. As long as you keep trying the next point in the halton sequence, your next try is always as far away from all previous tries as possible.

a_e_k 3y ago
The Halton sequence doesn't always choose the place where there's the most space left, except in the 1D case. If you plot 2D Halton sequence samples, you'll see the occasional sample placed fairly close to another, even when there's available space nearby. (Not that it doesn't do a decent job of generally filling in the empty areas.) Individually, it always selects a point where the 1D axial projections go in one the largest gap, but that doesn't mean that they're always exactly in the middle, nor that they jointly are in the largest space. An even simpler way than Halton for the 1D case, is to use the golden ratio. For that, you place sample j at (phi * j) mod 1.0, where phi is the golden ratio. (Or another way to think of it is to keep stepping forward from the last sample by phi with wrapping.) That really does always place each sample into the largest gap between all prior samples. You can use any irrational number as a multiplier and it will eventually sample the entire [0,1) space. But the golden ratio is optimal. See Kronecker sequences for the generalization to higher dimensions. (E.g., https://jcgt.org/published/0011/01/04/ https://jcgt.org/published/0011/01/04/) For higher dimensional sampling that really does try to place points in the middle of empty areas, have a look at Mitchel's "best candidate" algorithm (https://dl.acm.org/doi/10.1145/122718.122736 https://dl.acm.org/doi/10.1145/122718.122736). That basically goes something like this: to place point j: randomly choose j * m points (i.e., the candidates; m is a constant) find the one farthest from all prior placed points select and place that as point j It's slow and expensive, but it's designed precisely to try to find a large empty area and put a point in it, just as you mentioned. It's pretty general too, so you can do variations like computing the distances with toroidal wrapping, using non-Euclidean distance metrics, using any dimensional space you like, etc. It's also pretty common not to scale the number of candidates with j and just choose a constant number.

by mg 3y ago

a_e_k 3y ago

The Halton sequence doesn't always choose the place where there's the most space left, except in the 1D case. If you plot 2D Halton sequence samples, you'll see the occasional sample placed fairly close to another, even when there's available space nearby. (Not that it doesn't do a decent job of generally filling in the empty areas.) Individually, it always selects a point where the 1D axial projections go in one the largest gap, but that doesn't mean that they're always exactly in the middle, nor that they jointly are in the largest space. An even simpler way than Halton for the 1D case, is to use the golden ratio. For that, you place sample j at (phi * j) mod 1.0, where phi is the golden ratio. (Or another way to think of it is to keep stepping forward from the last sample by phi with wrapping.) That really does always place each sample into the largest gap between all prior samples. You can use any irrational number as a multiplier and it will eventually sample the entire [0,1) space. But the golden ratio is optimal. See Kronecker sequences for the generalization to higher dimensions. (E.g., https://jcgt.org/published/0011/01/04/ https://jcgt.org/published/0011/01/04/) For higher dimensional sampling that really does try to place points in the middle of empty areas, have a look at Mitchel's "best candidate" algorithm (https://dl.acm.org/doi/10.1145/122718.122736 https://dl.acm.org/doi/10.1145/122718.122736). That basically goes something like this: to place point j: randomly choose j * m points (i.e., the candidates; m is a constant) find the one farthest from all prior placed points select and place that as point j It's slow and expensive, but it's designed precisely to try to find a large empty area and put a point in it, just as you mentioned. It's pretty general too, so you can do variations like computing the distances with toroidal wrapping, using non-Euclidean distance metrics, using any dimensional space you like, etc. It's also pretty common not to scale the number of candidates with j and just choose a constant number.