Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Halton Sequence

en.wikipedia.org

Post reply on HN
Print view View original

1–10 of 11 posts

Re: Halton Sequence

#3

Post by matsadler »

I don't know why this caught HN's attention today, but I first found out about the Halton sequence a number of years ago when I needed a random seeming, regularly distributed and stable set of 2D points to sample an image, and the Halton sequence fit the bill precisely.

After implementing and benchmarking it I found my code was spending more time calculating the sample points than I'd like. When trying to speed that up I found this paper: https://www.sciencedirect.com/science/article/pii/0898122193...

Later when learning Rust I ported that faster approach to Rust: https://crates.io/crates/halton

And when I wrote a Rust library to bind Rust to Ruby, I created a Rubygem of the same as a testbed: https://rubygems.org/gems/halton

A few years ago I also put together a fun D&D game using the Halton sequence to place items/encounters on a map.

Re: Halton Sequence

#4

Post by [deleted] »

matsadler wrote: post #3

I don't know why this caught HN's attention today, but I first found out about the Halton sequence a number of years ago when I needed a random seeming, regularly distributed and stable set of 2D points to sample an image, and the Halton sequence fit the bill precisely. After implementing and benchmarking it I found my code was spending more time calculating the sample points than I'd like. When trying to speed that…

[deleted]

Re: Halton Sequence

#5

Post by mg »

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.

Re: Halton Sequence

#7

Post by tromp »

> Equivalently, the nth number of this sequence is the number n written in binary representation, inverted, and written after the decimal point

Shouldn't that be called the binary point? I would expect a decimal point to exist only in decimal notation...

Re: Halton Sequence

#8

Post by addaon »

tromp wrote: post #7

> Equivalently, the nth number of this sequence is the number n written in binary representation, inverted, and written after the decimal point Shouldn't that be called the binary point? I would expect a decimal point to exist only in decimal notation...

Yep. More generally, "radix point."

Re: Halton Sequence

#9

Post by a_e_k »

mg wrote: post #5

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_POI…

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

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

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.

Re: Halton Sequence

#10

Post by Solvency »

Is there a rule of thumb for when to use Halton sequence, versus Poisson distributions, versus Sobol sequences, versus Hell, I even see people use voronoi patterns to position points, which seems like overkill. Is it purely by choice/fascination?

It seems rather choose-your-own-poison, but wondering if there are any shorthand use-this-for-thats.

Post reply on HN