A Slice of Interdimensional Sponge Cake

The Menger sponge is a delightfully pathological shape to soak up. Start with a cube of side-length 1, and “hollow it out” by slicing it into 27 sub-cubes (like a Rubik’s Cube) and removing the 7 central sub-cubes as illustrated below. Call this the level 1 sponge. To make the 2nd level, perform the same “hollowing out” operation on each of the 20 cubes in level 1. Keep going to make levels 3, 4, and so on. The end result, i.e., level \(\infty\), is a fractal known as the Menger Sponge. It has a crazy[1] network of tunnels and passageways running through it:

Stages in the construction of the Menger sponge
Stages in the construction of the Menger sponge: Levels 0, 1, 2, and 3. Click for larger image.

What is its volume? We made the Menger Sponge by cutting out smaller and smaller chunks from the original unit cube, so how much volume did we leave behind? Each “hollowing out” step reduces the volume by a factor of 20/27, so level k has volume \((20/27)^k\) and the final Menger Sponge has volume 0. We removed all the volume!

Since the Menger Sponge doesn’t have enough “3D stuff” to be considered a truly 3-dimensional shape, maybe it behaves more like a 2-dimensional surface? This isn’t quite right either. The Menger Sponge has “too much 2D stuff”: its surface area is infinite.[2] In fact, this shape falls squarely (hah!) in the middle: it has dimension 2.7268….

Wait, what does it mean to have non-integer dimension? One interpretation, formalized in the notion of Hausdorff dimension, is to look at how the “stuff” it is made from behaves under scaling. If we take a square (which is made of “2-dimensional stuff”) and scale it by a factor of 1/3, its area changes by a factor of \((1/3)^2\). Similarly, scaling a cube (“3D stuff”) by 1/3 scales its volume by \((1/3)^3\). In general, scaling “d-dimensional stuff” by a factor of 1/3 scales its “d-dimensional volume” by \((1/3)^d\).

How a plane, Menger sponge, and cube behave under scaling
How different dimensional "stuff" behaves when scaled by a factor of 1/3. Left: A 2D plane is split into 9=3^2 smaller copies. Right: A 3D cube is split into 27=3^3 copies. Middle: A Menger sponge is split into 20 smaller copies.

As shown in this image, a Menger Sponge can be chopped into 20 smaller Menger Sponges, each scaled by 1/3. So if the Menger Sponge is made of m-dimensional stuff, its m-dimensional volume scales by 1/20 when the shape is scaled by 1/3, so we should have \((1/3)^m=1/20\), i.e., \(m=\log_3(20) = 2.7268\ldots\).

As one more example of the quirkiness that can be squeezed out of the Menger Sponge, what happens when we slice this shape along one of its primary diagonal planes[3]? The Menger Sponge’s crazy network of tunnels creates a stellar array of 6-pointed stars cut out of a regular hexagon:

A slice through a Menger sponge
Slicing a Menger sponge along a primary diagonal plane produces a dazzling fractal (living in the slicing plane) made from 6-pointed stars.

What is the Hausdorff dimension of this hexagonal fractal? It turns out to be $$\log_3\left(\tfrac{9+\sqrt{33}}{2}\right) = 1.8184\ldots.$$ To find out where this ridiculous number comes from, you’ll have to come back next week!


Notes

  1. This is a technical term, of course. []
  2. The surface area of level k can be computed to be \(2\cdot(20/9)^k+4\cdot(8/9)^k\), and this approaches infinity as k grows. []
  3. Specifically, slice it along the perpendicular-bisecting plane of one of the cube’s diagonals []

Dueling Dilettantes

[This is post #4 in a series on the Thue-Morse sequence. See posts #1, #2, and #3.]

What? You don’t agree that the Thue-Morse sequence is awesome? OK, there’s only one way to settle this dispute: I challenge you to a duel. This unfortunately might take a while, because we both have terrible aim.

Let’s say we both have the same probability \(p=.2\) of hitting our target on any given shot, and the first to hit is the winner. I’ll even be gracious and let you go first, and I’ll shoot second. In the first two shots of the game, the probability that you win (i.e., hit your first shot) is \(p=.2\), and the probability that I win (i.e., you miss and then I hit) is \((1-p)\cdot p = .16\). (In the remaining probability \(1-.2-.16=.64\), the duel continues.) This means that you are more likely to win during the first two shots than I am, so it should only be fair that I take the third shot!

How do the probabilities look in the first three shots? Your chances of winning are still \(p=.2\), while mine are \((1-p)\cdot p + (1-p)^2\cdot p = .288\) because I might win on the second or third shot. Now it seems that I have the advantage, so you should take the 4th shot in the interest of fairness. Let’s continue like this, choosing to give the 5th shot to the theoretical underdog from the first 4 rounds, the 6th shot to the underdog in the first 5 rounds, and so on.

You can (and should!) check that the shot order will be Y, M, M, Y, M, Y, Y, M, M, Y,  M, Y, Y, M, M, Y, ..., where Y=You and M=Me. Does that sequence look familiar? The first 10 digits look suspiciously like the start of the Thue-Morse sequence, but I don’t recognize the rest of it. Did we make a computation error? Hmm…

The problem, as it turns out, is that our aim is too good! What happens if we make ourselves worse by, say, standing farther apart? Let’s say we now have a \(p=.1\) chance of hitting our mark on each shot. What is the “fair” shot order this time? Our duel will now follow the sequence Y, M, M, Y, M, Y, Y, M, M, Y, Y, M, Y, M, M, Y, M, Y, Y, M,  M, Y, Y, ... which matches the Thue-Morse sequence in the first 20 digits. Similarly, setting \(p=.05\) gives 48 correct Thue-Morse digits, defining \(p=.01\) gives 192 correct Thue-Morse digits, and decreasing to \(p=.001\) gives 1536 matching digits! It can in fact be proved[1] that decreasing \(p\) toward 0 (i.e., making our aim worse) gives more and more Thue-Morse digits, with the full Thue-Morse sequence appearing in the limit.

See? Even when arguing about whether the Thue-Morse sequence is cool, we find evidence of its greatness! I hereby declare myself the winner of this duel.

This concludes our series on the Thue-Morse sequence. Tune in next week for, well, something else!


Notes

  1. Joshua Cooper and Aaron Dutle. Greedy Galois Games. ArXiv, 2011. []

Chess, Bored

[This is post #3 in a series on the Thue-Morse sequence, which was introduced two weeks ago and discussed further last week.]

While the Thue-Morse sequence appears in many branches of Mathematics[1], this sequence has also captured a place in the history of chess.

With only the basic rules of chess (specifically, how pieces move and capture and how a game may end by checkmate or stalemate), there is no guarantee that a game of chess will ever finish. For example, two (very bored!) players could theoretically move their knights back and forth ad infinitum without ever engaging each other or capturing a piece (but why would they want to?). A more realistic example is drawn below. In this game, black will soon checkmate white if given the freedom to move, and white has no way to win. However, white can avoid losing by keeping black in an unending runaround with repeated checks, as illustrated. In this case (a phenomenon known as perpetual check), forcing an infinite game is more advantageous for white than allowing an otherwise inevitable loss.

Perpetual Check
Animation frames were made with the WiseBoard Chess Board Editor.

Because of this possibility of never finishing, a search began for new chess rules to guarantee that every game of chess eventually ends. One suggested rule was:

A chess game ends with a draw if a sequence of moves—with all pieces in exactly the same positions—is played three times successively.[2]

The hope was that any sufficiently long chess game would eventually repeat itself enough to break this rule. However, as Mathematician and Chess Grandmaster Max Euwe showed in 1929[3], this hope is not correct. Indeed, there exist infinite chess games that never repeat the same block of moves three times in a row!

How did he prove this? With the Thue-Morse Sequence, of course! He proved the very unintuitive fact that the Thue-Morse sequence has no chunk repeated three times consecutively. Such a thrice-repeated sequence is called a cube, so this property can be restated by saying that the Thue-Morse sequence is cube-free. For example, you will never find the sequences 1 1 1 or 011 011 011 in the Thue-Morse sequence. (Challenge: show that these two sequences do not appear. Harder challenge: show that the Thue-Morse sequence is cube free!) So, if the “very bored” knight-flippers described above decide to move their right knights or left knights according to the 1s and 0s of the Thue-Morse sequence, the resulting game will have no tripled move sequences.

Luckily, the above rule is not part of the current official chess rule set. There are now two rules on the books that can be used to eventually end any chess game. (In fact, either one would suffice. [Prove this!]) A draw may be declared in either of these situations:

  • The exact same board position appears three times ever during a game. (Every detail must be the same, such as whose turn it is, which kings have the ability to castle, etc.)
  • No pawn is moved and no piece is captured in 50 consecutive turns. (A turn consists of one move by each player.)

However, there’s (always) a catch. These two rules only take effect if a player notices and decides to declare a draw. So even with all modern rules in effect, the bored knight-flippers are still allowed to play their infinite game of chess—cube-free or not.


Notes

  1. A great survey called The ubiquitous Prouhet-Thue-Morse sequence by Allouche and Shallit documents many sightings of this sequence throughout Mathematics, including Combinatorics, Differential Geometry, Number Theory, Analysis, and as discussed here, Combinatorial Game Theory. []
  2. Manfred Börgens, Max Euwe’s sequence []
  3. in his paper titled Mengentheoretische Betrachtungen über das Schachspiel []

Thue-Morse-igami

Here’s a simple origami experiment to try. Start with a long strip of paper with different colors on the two sides—e.g., Orange (O) on one side, Indigo (I) on the other. Now fold the strip in quarters to form a flat “S-shape” as illustrated here (creases are drawn slightly rounded for ease of viewing):

Folding the Thue-Morse sequence, level 1

As you look through the four layers from top to bottom, write down the colors you encounter, in order: the first layer shows Indigo (I), the second layer has Orange (O), and so on. The full order is IOOI, which looks suspiciously like the start of the Thue-Morse sequence. (This sequence was introduced last week.)

To continue the experiment, treat this figure as a single strip and fold the same flat S-shape again. There will be 16 layers down the middle:

Folding the Thue-Morse sequence, level 2

Sure enough, the order of colors encountered is IOOI OIIO OIIO IOOI, which is the first 16 digits of the Thue-Morse sequence. This pattern will continue forever (or at least until the paper gets too thick to fold): every time you fold another S-shape, you quadruple the number of digits of the Thue-Morse sequence (can you see why?). Try to fold a third iteration! It looks like this (click for larger image):

Folding the Thue-Morse sequence, level 3

But wait, there’s more! Now that we have these creased strips, what happens when we unfold them? Specifically, follow the existing creases and lay out the strips so that each crease makes a 90-degree angle. What shapes do we get? Surprisingly, they exactly fill triangular grids of squares:

Unfolding the Thue-Morse-folded strips

Can you figure out why this pattern continues?

Thue-Morse Navigating Turtles

Here’s a simple rule to generate a pretty sequence of 1s and 0s: Start with the list 1 (just one digit) and repeatedly form a new list by flipping all the bits (1s become 0s and vice versa) and attaching this to the end: $$1 \to 10 \to 1001 \to 10010110 \to 1001011001101001 \to \cdots.$$ For example, to get from 1001 to the next sequence, we swap 1s and 0s to form 0110, and then we join these together to make 10010110. By continuing this process we can make our list longer and longer, and the limiting sequence $$1001011001101001011010011001011001101\cdots$$ is called the Thue-Morse Sequence.

What did I mean by calling this sequence “pretty”? Well, what does this sequence “look like”? One way to visualize it is with a turtle program. Imagine a turtle (let’s call him Leo) walking along the plane, and treat the digits of the Thue-Morse sequence as a list of instructions for the turtle as follows: When Leo sees the digit 1, he steps forward one foot; a 0 tells Leo to turn left by 60 degrees. What does Leo’s path look like? Here are the first 32 instructions he follows:

Turtle Program for the Thue-Morse Sequence
The turtle follows these instructions on the first 32 entries of the Thue-Morse sequence: {1: Step; 0: Turn 60}.

And here are snapshots of his path as he gets farther into the Thue-Morse sequence:

Turtle Program Trajectories for the Thue Morse Sequence: rule 1
Snapshots of the turtle's trajectories after 2^8, 2^10, 2^12, and 2^14 instructions, respectively.

Why did we pick these instructions? What if Leo turns 120 degrees instead of 60 degrees when he sees a 0?

Another Turtle Program for the Thue-Morse Sequence
The turtle follows the Thue-Morse sequence with a slightly different set of instructions: {1: Step; 0: Turn 120}. Shown here after 2^6, 2^8, 2^10, and 2^12 instructions, respectively.

If you zoom out and/or squint a little, these paths are roughly following a famous fractal called the Koch curve. And indeed, the more steps you draw, the closer the resemblance will become (as analyzed in these two papers: [MH2005] and [KZH2008]). But why stop here? What happens if we change the turtle’s instructions even more? I played around with some new rule sets, and these too show how the Koch curve seems innately “programmed” into the structure of the Thue-Morse sequence:

Other Turtle Programs for the Thue-Morse Sequence
Three more pretty examples of the Thue-Morse sequence's "turtle power." In all three cases, the trajectories converge to the Koch curve. Left: {1: (Turn 180, Step); 0: (Turn 60, Step)}, after 2^8 instructions. Middle: {1: (Turn 180, Step); 0: (Turn 120, Step)}, after 2^10 instructions. Right: {1: Turn 180; 0: (Turn 15, Step)}, after 2^10 instructions.

Here’s a final challenge: if the Koch curve and the Thue-Morse sequence are so intimately related, shouldn’t we be able to find some turtle program instructions that trace the Koch curve without “squinting”? Specifically, the Koch curve is usually constructed as the limit of the following sequence of paths, where each iteration is made by stitching together four copies of the previous curve:

The Koch Curve
The Koch curve is constructed as the limit of these paths, where each curve is formed from four (shrunken) copies of the previous curve.

Is there a set of turtle instructions whose path traces exactly these curves? In fact, there is! These instructions work: {1: (Step, Turn 60); 0: Turn 180}.

A Balancing Fact

Enough geometry already! Let’s switch gears and explore an interesting phenomenon in balanced grid coloring:

Problem: The numbers 1,2,…,100 are written in order in a \(10\times 10\) grid. Some grid cells are colored red, and the rest blue, in such a way that exactly half the cells in each row and each column are red (call this a balanced coloring). Show that the sum of the numbers in red cells equals the sum of the numbers in blue cells.

Examples of Balanced Grids
Examples of balanced grids: each grid has five red and five blue cells in each row and column. By the problem above, the red numbers and blue numbers add to the same total in each grid.

How can we understand this question? Notice that each row needs five red and five blue cells, but the values in each row do not need to balance. Indeed, the first row of the first example above is very skewed toward blue: \(\text{red}=1+2+3+4+5=15\) and \(\text{blue}=6+7+8+9+10=40\). In fact, every row in that example is very skewed to one side or the other! But the fact that every column also needs five red and five blue numbers somehow forces these skewed row sums to cancel each other out. This is essentially what the problem asks us to prove.

A (Not So Great) Start

Here’s one idea: let’s just test all the balanced grid colorings! There can’t be too many, right? Let’s start small. How many balanced \(2\times 2\) grid colorings are there? (Each row needs 1 red and 1 blue.) Just two: the first cell is either red or blue, and everything else is determined from there (cf. binary sudoku). And each of these has a red sum and a blue sum of 5, so we’ve verified the problem for \(2\times 2\) grids. What about \(4\times 4\)? With a little work, you can compute by hand that there are 90 balanced colorings of a \(4\times 4\) grid (try this!). That’s already a lot of cases to check. For \(10\times 10\) grids, it turns out that there are 6736218287430460752 balanced colorings! Maybe it’s time to look for a different method.

A Solution

Here’s a method that does work. Start with a zero in each grid cell; the red and blue sums are certainly equal (they’re both zero). Now we’ll modify the values one row or column at a time. If we add 1 to each cell in a column, then the red and blue sums each increase by 5 (because each column is balanced), so the sums remain equal. Do this once in the first column, twice in the second column, and so on, resulting in the middle grid below (which must therefore have equal red and blue sums):

Solution to the Balanced Grid Problem
Adding the same number to each cell in a row or column of a balanced grid keeps the red and blue sums equal. Applying this process to an initially all-zero grid yields the desired grid of 1,2,...,100 and solves the problem.

Now modify the rows: add 10 to the second row, 20 to the third row, etc., finally ending up with the numbers 1,2,…,100 in order. Each step preserves the fact that the red and blue sums match, so we’re done! Notice that this argument works for any even grid size; 10 is not special here.

About This Problem

This problem appeared (with different phrasing) in the 2001 Putnam Competition, a very challenging mathematics competition for undergraduate students in the United States and Canada. This competition’s directories contain even more solutions and insights into this problem (Problem 2001 B1).

Spherical Surfaces and Hat Boxes

To round off our series on round objects (see the first and second posts), let’s compute the sphere’s surface area. We can compute this in the same way we related the area and circumference of a circle two weeks ago. Approximate the surface of the sphere with lots of small triangles, and connect these to the center of the sphere to create lots of triangular pyramids. Each pyramid has volume \(\frac{1}{3}(\text{area of base})(\text{height})\), where the heights are all nearly \(r\) and the base areas add to approximately the surface area. By using more and smaller triangles these approximations get better and better, so the volume of the sphere is $$\frac{4}{3}\pi r^3 = \frac{1}{3}(\text{surface area})\cdot r,$$ meaning the surface area is \(4\pi r^2\). (This and previous arguments can be made precise with the modern language of integral calculus.)

Dividing a sphere into many pyramids
Dividing a sphere into many pyramids connected to the center allows us to relate the sphere's surface area and volume.

Here’s an elegant way to rephrase this result: The surface area of a sphere is equal to the area of the curved portion of a cylinder that exactly encloses the sphere. In fact, something very surprising happens here!:

Archimedes’ Hat-Box Theorem: If we draw any two horizontal planes as shown below, then the portions of the sphere and the cylinder between the two planes have the same surface area.

Archimedes' Hat-Box Theorem
Any two horizontal planes cut off a band on the sphere and another band on the enclosing cylinder. Archimedes' Hat-Box Theorem says that these bands have the same area. (The planes shown here have heights \(0.4\cdot r\) and \(0.6\cdot r\) above the equator.)

We can prove this with (all!) the methods in the last few posts; here’s a quick sketch. To compute the area of the “spherical band” (usually called a spherical zone), first consider the solid spherical sector formed by joining the spherical zone to the center:

Spherical sector
The Hat-Box theorem can be proved by relating the area of the spherical zone to the volume of this spherical sector.

By dividing this into lots of triangular pyramids as we did with the sphere above, we can compute the area of the spherical zone by instead computing the sector’s volume. This volume can be computed by breaking it into three parts: two cones and the spherical segment between the two planes (on the left of the next figure). Compute the volume of the spherical segment by comparing (via Cavalieri’s Principle) to the corresponding part of the vase (from the previous post), which can be expressed with just cylinders and cones.

Volume of a spherical segment via Cavalieri's Principle
Computing the volume of a spherical segment via Cavalieri's Principle

See if you can fill in the details!

Slicing Spheres

Last week we saw how to compute the area of a circle from first principles. What about spheres?

To compute the volume of a sphere, let’s show that a hemisphere (with radius \(r\)) has the same volume as the vase shown in the figure below, formed by carving a cone from the circular cylinder with radius and height \(r\). Why this shape? Here’s why: if we cut these two solids at any height \(h\) (between 0 and \(r\)), the areas of the two slices match. Indeed, the slice—usually called cross section—of the sphere is a circle of radius \(\sqrt{r^2-h^2}\), which has area \(\pi(r^2-h^2)\). Similarly, the vase’s cross section is a radius \(r\) circle with a radius \(h\) circle cut out, so its area is \(\pi r^2-\pi h^2\), as claimed.

Hemisphere and vase cross sections
When sliced by a horizontal plane at any height \(h\), the hemisphere and vase have equal cross-sectional areas. (Shown here for \(h = 0.4\cdot r\).) By Cavalieri's Principle, this implies that they have equal volumes.

If we imagine the hemisphere and vase as being made from lots of tiny grains of sand, then we just showed, intuitively, that the two solids have the same number of grains of sand in every layer. So there should be the same number of grains in total, i.e., the volumes should match. This intuition is exactly right:

Cavalieri’s Principle: any two shapes that have matching horizontal cross sectional areas also have the same volume.

So the volumes are indeed equal, and all that’s left is to compute the volume of the vase. But we can do this! Recall that the cone has volume \(\frac{1}{3} (\text{area of base}) (\text{height}) = \frac{1}{3}\pi r^3\) (better yet, prove this too! Hint: use Cavalieri’s Principle again to compare to a triangular pyramid). Likewise, the cylinder has volume \((\text{area of base}) (\text{height}) = \pi r^3\), so the vase (and hemisphere) have volume \(\pi r^3 – \frac{1}{3} \pi r^3 = \frac{2}{3}\pi r^3\). The volume of the whole sphere is thus \(\frac{4}{3}\pi r^3\). Success!

The following visualization illustrates what we have shown, namely $$\text{hemisphere} + \text{cone} = \text{cylinder}.$$ The “grains of sand” in the hemisphere are being displaced horizontally by the stabbing cone, and at the end we have exactly filled the cylinder.

Stabbing a cone into a hemisphere
Stabbing a cone into a hemisphere made of horizontally-moving "sand particles" exactly fills a cylinder.

Archimedes’ Circular Reasoning

Every geometry textbook has formulas for the circumference (\(C = 2 \pi r\)) and area (\(A = \pi r^2\)) of a circle. But where do these come from? How can we prove them?

Well, the first is more a definition than a theorem: the number \(\pi\) is usually defined as the ratio of a circle’s circumference to its diameter: \(\pi = C/(2r)\). Armed with this, we can compute the area of a circle. Archimedes’ idea (in 260 BCE) was to approximate this area by looking at regular \(n\)-sided polygons drawn inside and outside the circle, as in the diagram below. Increasing \(n\) gives better and better approximations to the area.

Approximating circle area with triangles
The n-sided regular polygons inside (blue) and outside (red) a circle can be used to approximate the area of the circle. Shown here for n=12.

Look first at the inner polygon. Its perimeter is slightly less than the circle’s circumference, \(C = 2 \pi r\), and the height of each triangle is slightly less than \(r\). So when reassembled as shown, the triangles form a rectangle whose area is just under \(C/2\cdot r = \pi r^2\). Likewise, the outer polygon has area just larger than \(\pi r^2\). As \(n\) gets larger, these two bounds get closer and closer to \(\pi r^2\), which is therefore the circle’s area.

Archimedes used this same idea to approximate the number \(\pi\). Not only was he working by hand, but the notion of “square root” was not yet understood well enough to compute with. Nevertheless, he was amazingly able to use 96-sided polygons to approximate the circle! His computation included impressive dexterity with fractions: for example, instead of being able to use \(\sqrt{3}\) directly, he had to use the (very close!) approximation \(\sqrt{3} > 265/153\). In the end, he obtained the bounds \( 3\frac{10}{71} < \pi < 3\frac{1}{7} \), which are accurate to within 0.0013, or about .04%. (In fact, he proved the slightly stronger but uglier bounds \(3\frac{1137}{8069} < \pi < 3\frac{1335}{9347}\). See this translation and exposition for more information on Archimedes’ methods.)

These ideas can be pushed further. Focus on a circle with radius 1. The area of the regular \(n\)-sided polygon inscribed in this circle can be used as an approximation for the circle’s area, namely \(\pi\). This polygon has area \(A_n = n/2 \cdot \sin(360/n)\) (prove this!). What happens when we double the number of sides? The approximation changes by a factor of $$\frac{A_{2n}}{A_n} = \frac{2\sin(180/n)}{\sin(360/n)} = \frac{1}{\cos(180/n)}.$$ Starting from \(A_4 = 2\), we can use the above formula to compute \(A_8,A_{16},A_{32},\ldots\), and in the limit we find that $$\pi = \frac{2}{\cos(180/4)\cdot\cos(180/8)\cdot\cos(180/16)\cdots}.$$ Finally, recalling that \(\cos(180/4) = \cos(45) = \sqrt{\frac{1}{2}}\) and \(\cos(\theta/2) = \sqrt{\frac{1}{2}(1+\cos\theta)}\) (whenever \(\cos(\theta/2) \ge 0\)), we can rearrange this into the fun infinite product $$\frac{2}{\pi} = \sqrt{\frac{1}{2}} \cdot \sqrt{\frac{1}{2}+\frac{1}{2}\sqrt{\frac{1}{2}}} \cdot \sqrt{\frac{1}{2}+\frac{1}{2}\sqrt{\frac{1}{2}+\frac{1}{2}\sqrt{\frac{1}{2}}}} \cdots$$ (which I found at Mathworld). (It’s ironic that this formula for a circle uses so many square roots!)

Voronoi Cells on a Plane

As a pilot of an (oversimplified) airplane, you may want to know how to communicate with the nearest control tower to receive information on local weather, air traffic, and so on. Each control tower has some region of the map that it “controls,” i.e., where it is closer than any other tower. An example is drawn below. These regions are known as the Voronoi regions (or Voronoi cells) of the points, and the whole diagram is the Voronoi decomposition determined by those points.

Example Voronoi decomposition
The Voronoi diagram of 20 randomly chosen points in a square

For a given set of points, we can imagine the corresponding Voronoi regions as follows: grow disks around the points at the same rate, stopping when they hit each other. A disk collides with other disks exactly when its center ceases to be closest, so these regions are indeed the Voronoi cells.

Generating Voronoi cells by growing circles
The Voronoi cells can be created by growing circles around the points.

Now let’s kick this into third gear—by which I mean the third dimension. In the animation above, suppose that the circles were moving downward over time, producing a cone below each point. By looking at these cones from above, we see exactly the Voronoi regions! Since cones are easy for computers to render, this provides a handy trick for quickly drawing Voronoi decompositions. In fact, this is how I drew all of these images!

Voronoi regions from cones
By placing identical, vertical cones under the points, one sees the corresponding Voronoi regions from directly above.

This construction is not only of theoretical value, but has also been put to good use packaging Ferrero Rocher chocolates:

Voronoi regions in Ferrero Rocher packaging
Voronoi regions in Ferrero Rocher packaging

Who knew these (delicious!) spherical candies were so mathematical?