Last year I blogged about a program I had written to calculate the nearest capital.

It just occurred to me that once the area being the closest to a given capital has been established, the capital can then be moved to the centre of this area, and the process can be repeated.

In this way, the countries shift gradually until they have reached an equilibrium:

In general, the resulting “countries” are more or less the same size, but obviously the shape of the coastline has interesting consequences.

This is known as Lloyd’s algorithm:

http://en.wikipedia.org/wiki/Lloyd%27s_algorithm

Thanks!

Isn’t it sometimes frustrating in computer science that you can come up with an algorithm independently, only to find out that it would have been named after you if you had done so a few decades earlier? 🙂