Suppose you want to divide a numeric range (such as 0–1 or 0–23 or 1–365) into even segments. If you know how many segments you have, it's easy; you divide by N. But if you don't know how many segments you will have, and you can't go back once you've divided something, it gets trickier. If you divide into 3 equal segments and need 3, you're at the optimal point. But if you instead need 4 and have already divided into 3 segments, you end up subdividing one segment of length 1/3 into 2, leaving you with 4 segments of length 1/6, 1/6, 1/3, and 1/3.

There's a clever division scheme involving the golden ratio:

  1. Rescale your range to be from 0–1.
  2. The ith division occurs at i * φ

It's so simple. Why does this work? I don't know. But it's pretty neat.

I first ran across this when I was looking for a way to pick sample points in 1 year of data. I wanted a set that would be roughly evenly spaced, because I wanted to draw a timeseries chart with the results, but I didn't know how much time it would take to analyze the points. So I analyzed one at a time, using the golden ratio to guide me.

7 comments:

Alok wrote at Tuesday, July 31, 2007 at 4:01:00 PM PDT

The Golden Ratio (Phi) is greater than zero (1.6...).

If the i th division is given by phi * i, would be greater than 1, wouldn't it? Where would that slice in your rescaled range of 0-1?

Also, this still leaves the problem of *uneven* slices.

Amit wrote at Tuesday, July 31, 2007 at 4:04:00 PM PDT

Yes, you're right — I meant to take the fractional component of i * φ.

They're still uneven but it's unavoidable. This scheme leaves them as even as possible (I think) given the constraint that they need to be roughly even after each division.

Bhasker Hariharan wrote at Thursday, August 2, 2007 at 8:44:00 AM PDT

Amit,

Just wanted to let you know that over the years I have found some of the material on your website really useful. I am a hobbyist game programmer(wannabe is more like it) but I really enjoy reading some of your articles on pathfinding etc.

BTW how is supreme commander:D Have to upgrade my system to handle the damn game.

Anonymous wrote at Friday, August 3, 2007 at 5:26:00 AM PDT

This is a recasting of the familiar link between the golden ratio and phyllotaxis; successive leaves are in a certain sense as far as possible from previous ones if they are separated by the previous one by an angle of 360°/(1+φ), about 137.5°.
See:
Stephen Wolfram, "A new kind of science" §8.6 at http://www.wolframscience.com/nksonline/toc.html
http://en.wikipedia.org/wiki/Golden_angle
http://en.wikipedia.org/wiki/Fermat%27s_spiral

Amit wrote at Sunday, August 5, 2007 at 4:56:00 PM PDT

Thanks anonymous! Yes, using the fractional component connects this problem to the cyclical nature of the golden angle. BTW, plants may not necessarily follow the golden ratio and Fibonacci sequence.

Blogumdan wrote at Friday, May 23, 2008 at 5:53:00 AM PDT

They're still uneven but it's unavoidable. This scheme leaves them as even as possible (I think) given the constraint that they need to be roughly even after each division.

Amit wrote at Saturday, December 29, 2012 at 4:43:00 PM PST

Also see Equidistribution Theorem