Circle Packing 2: Explanation

Circle Packing 2 another variation of the Circle Packing algorithm. This time, we take interest in what goes on during the creation of a new circle.

This version has been tweaked to be more informative. The display rules are the following:

  • Upon creation, circles appear black; this indicates a “hit”
  • Every time a circle is created, all the other circles fade a bit;
  • When circles are created, their initial position is chosen at random. if this position is occupied by a circle, that circle is allowed to appear; this indicates a “miss”. Another tentative point is then chosen;
  • The animation stop when too many points have been tried and are occupied by circles.

The flaws of my algorithm appear clearly with this visualization mode. Ideally, we would only see black dots appear and then gradually fade out. In the very beginning, this is the case: the vast majority of points are black. Then, gradually, as the available space shrinks, the black dots become smaller and smaller, indicating that real estate is scarcer. While that happens, more and more colored circles appear and fade out, indicating “misses”. At the very end of the execution, misses outnumber hits by several orders of magnitude, lighting up the screen with a many colored circles.

It is not a coincidence that throughout the execution, the largest circles are almost always lit up: they occupy a lot of space, and so they have more probability of being “bothered” by a new circle trying to pop up.

This algorithm is analogue with real-life situations:

  • The more important you are, the more you are solicited - and the more visibility you have;
  • As resources/land become scarcer, their cost increases; in this case, the cost is represented by the number of misses before a hit is found and the circle is allowed to appear.
  • The first people to enter a domain quickly take control of a large portion of that domain;
  • A small minority of individuals own the bulk of the resources. The small remainder is shared by a large number of individuals;
  • Growth is limited by available resources and other individuals;
  • If individuals require a minimum amount of resources to exist, then eventually, there are no resources left to allow new individuals to appear. In this case, the circles have a minimum radius. If that weren’t the case, a new circle could always find room somewhere in between other circles, indefinitely.

I have an idea for a more efficient Circle Packing algorithm, but I haven’t implemented it… yet.

January, 2008.