Navigating Hyperbolic Space with Fibonacci Trees

When moving from the usual Euclidean flat space to a curved space like hyperbolic space, one not only has to work with new models of basic geometric concepts like points, lines, and triangles, but one also has to deal with new ways of counting.  When creating software that deals with space, ways of counting in space are of utmost importance because counting forms the basis for the design of compact and efficient data structures.

For example, software dealing with particle systems and forces between particles must have a mechanism for spatial partitioning in order to mitigate the combinatorial explosion of particle-particle interactions and make the system computationally tractable.  In 2D space, this is typically done with a tree-based data structure such as a quadtree or in 3D an octree.  These data structures are based on a linear counting that tracks the structure of how flat space divides in to smaller pieces.

In hyperbolic space, however, space does not divide so neatly due to the exponential growth in the size of the space as one moves from a reference point.  Instead, what is needed is counting mechanism that tracks the exponential nature of hyperbolic space.

So how might we go about constructing a counting system for hyperbolic spaces in order to design hyperbolic data structures?  First, we can look at the fundamental work on hyperbolic spaces by Coxeter in which he links hyperbolic tiling to group theory, which has been extended in to computational group theory.  The process of tiling is in a sense a kind of counting just like group theory can be boiled down to arithmetic on the integers, but it still doesn’t quite show us how to build data structures over the tilings.  For that, we need to develop a coordinate system over the tiles so that we can quickly construct neighborhoods around a particular cell and navigate from one cell to another along a shortest path.  This is where Maurice Margenstern‘s hyperbolic cellular automata comes in.

In developing hyperbolic cellular automata, Margenstern has developed a way of overlaying a coordinate system over the hyperbolic tilings (5, 4) and (7, 3).  The critical insight is that the Fibonacci sequence maps perfectly to the sectors of the hyperbolic tile where one sector corresponds to a the tiles connected to one side of the central polygon.  In the (5, 4) tiling, there are 5 sectors and thus 5 Fibonacci sequences covering the tiling.  The Fibonacci series maps on to the tilings through a tree structure where the coordinates of child, parent, and sibling nodes can be calculated by working with simple operations on Fibonacci numbers.

The image above shows a single pentagonal sector with its corresponding Fibonacci tree.  The tree is constructed with 2 simple riles: each white node has children (black, white, white) and each black node has children (black, white).  The square at the top of the tree is the fundamental polygon, which links together the 5 trees of the complete tiling.  Interestingly, the resulting Fibonacci tree is a 2-3 tree, which is a data structure in computer science that creates well-balanced trees, making modification and searching efficient.

Notice that the indices in the tree nodes count like normal integers and not like Fibonacci numbers.  Here, the Fibonacci sequence doesn’t define the way that nodes are counted but instead the way that integers are assigned to them and the way the tree is structured.  For instance, each row of the tree has F[2*n+2] nodes where F[n] is the nth Fibonacci number.

There is a well-known way to represent integers with Fibonacci numbers called the Zeckendorf representation.  The Zeckendorf theorem states that any integer can be represented uniquely by a set of non-consecutive Fibonacci numbers.  As a result, any integer can be written as a binary number where each bit corresponds to an index in the Fibonacci sequence.  For example, 14 can be written as 13+1.  The Zeckendorf representation of 14 is therefore 100001.  7 is 5+2 or 1010.  What Margenstern realized is that the parent-child relationships of nodes in the tree covering the hyperbolic tilings (5, 4) and (7, 3) can be calculated using the Zeckendorf representation of the integers since the structure of the tree follows a Fibonacci growth pattern.  For example, node 2 has children 5 and 7.  In Zeckendorf notation, 2=10, 5=1000, and 7=1010.  The children of 2 are it’s Zeckendorf representation with 00 and 10 tacked on in the end.  This pattern generalized to all black nodes (those with 2 children).  The complete set of rules for white and black nodes can be found in Margenstern’s paper Cellular Automata in the Hyperbolic Plane: Proposal for a New Environment.

The Zeckendorf counting generalizes beyond describing parent child relationships to describing in a simple closed form all of the connections a particular tile has to neighboring tiles.  This gives not only a way of constructing a hyperbolic coordinate system, but a way of easily navigating hyperbolic space without having to explicitly model the connections themselves, saving both memory and computation.

Based on Zeckendorf counting, we can also build intuitive hyperbolic interfaces for interacting with data in hyperbolic space.  Here, the idea is to place whatever data is being inspected in the central polygon and have its neighborhood represented in the surrounding visible region.  This is essentially the problem of mapping one tree on to another.  The first tree is rather small and is for structuring the spatial layout defining the number of cells visible at any given moment.  The second tree can be infinite in size and contains the data to be displayed.  I won’t describe the mapping algorithm in detail here, but it suffices to say that the mapping is made extremely simple through the manipulation of Zeckendorf counting.  

Above are 2 examples of mapping a data tree onto a display tree.  The first maps the cell (0:0) into the central polygon.  I’ve colored each of the 5 sectors with a different color to distinguis the 5 trees.  Since (0:0) is the original coordinate of the central polygon anyway, the mapping is trivial.  Notice that each edge from the central polygon to its children is a different color.  This is because the central polygon links together all 5 trees.  The the second example, the central node is (3:2), that is the 2nd node of the 3rd tree.  Notice how almost the entire graph of connections is blue.  When (3:2) was shifted to the center, the focus moved from all trees to the 3rd tree, so nodes from the 3rd tree shifted into the surrounding neighborhood, leaving only a few cells of the 2nd tree visible at the top.  Also, cell (0:0) has moved into what used to be cell (1:2) in the top right.

This entry was posted in Computational Technique, Space and Geometry and tagged , , , . Bookmark the permalink.

Leave a Reply