Exploring recursion in Hilbert curves.
Richard Rasala · 2001
This tip will describe the use of a graphical tool to explore the recursive Hilbert curves and will explain some of the mathematical information that can be visualized using this tool. 1. Brief History The sequence of recursive Hilbert curves was discovered by the mathematician David Hilbert about 100 years ago in order to answer the Space Filling Curves Problem. In its simplest version, this problem asks if there exists a continuous function from the unit interval [0, 1] that maps onto the unit square in the plane. The answer is yes and the sequence of Hilbert curves gives a constructive definition of the function. To obtain the function, one must “pass to the limit ” as the level N of recursion goes to infinity. Hilbert curves became well known in the computer science community because Nicklaus Wirth used them as a key example of recursion in his fundamental text [2]. 2. Interactive Exploration of Hilbert Curves We have developed an interactive demonstration program that enables a student to explore Hilbert curves through several related visualizations. Students can: 1. Draw the curves. 2. Add arrows to show the direction of traversal. 3. Add background blocks to show how the curves relate to a tiling of the unit square. 4. Number the tiling blocks so that it is possible to see what happens during passage to the limit. In the screen image below, the Hilbert curve of level 3 is shown on top of the tiling of level 3. It is clear that the nodes of the curve are at the centers of the tiling blocks. On top of this drawing, we have placed the block labels for levels 1, 2, 3. These labels are digit sequences in base 4. The digit sequences may be interpreted as the leading digits in the base 4 fractional expansion of a number between 0 and 1. Consider the digit sequence 312 for example. This corresponds to a square in the lower right of the image. The meaning of the label 312 is that all points x in the interval [0, 1] whose leading digits (base 4) are 312 will land in the block labeled 312 under the Hilbert mapping.