# Good data structure for hyperbolic tiling [duplicate]

This question already has an answer here:

Say you're doing something computational where each data point is a tile in a (not necessarily Euclidean) 2-dimensional tiling, for instance, a Life-like cellular automata. You might want a data structure where tiles that are near in distance are also near each other in memory. You might choose your tiling based on what's easy to represent this way.

For a tiling of the Euclidean plane, you probably have square tiles backed by a 2d array with array point a[i][j] = tile $a_{ij}$; you might have hex tiles instead, which can also be backed by a 2d array as explained in http://www.redblobgames.com/grids/hexagons/.

For a tiling of the sphere, it's pretty common to start with a sub-triangulation of the icosahedron and subdivide it into 5 2d arrays plus 2 points for the north pole, as explained in http://kiwi.atmos.colostate.edu/BUGS/geodesic/text.html. It looks like a geodesic dome.

Is there a 2d hyperbolic tiling that admits a representation in a nice data structure? The only software I've ever seen that uses hyperbolic tiling in this way is the game HyperRogue (a roguelike on the hyperbolic plane). It just has an object for each tile, and each tile keeps a record of its neighbors. It works but it's not pretty.

## marked as duplicate by PyRulez, user284331, Ethan Bolker, GNUSupporter 8964民主女神 地下教會, SaadMar 15 '18 at 0:27

My approach was the following: choose a central triangle, and label the reflections in its edges as $a,b,c$. Then every triangle in the tiling is the result of that central triangle after some sequence of these operations has been applied. So every string consisting of these three letters, possibly with repetitions, describes a single triangle. Conversely, for every triangle there will be several strings (corresponding to different paths from the center to the given triangle), but these strings can be ordered (e.g. using shortlex ordering) so you can choose the minimal one as the canonical representative of that triangle.