# Symbolic coordinates for a hyperbolic grid?

Rephrasing     (one year later)    (original question is below)
Apparently the original question wasn't clear, or nobody knows an answer (or both). So I will try to rephrase it.

Look at your favorite hyperbolic grid. This question asks for a labeling system for the points.

Of course we could draw the grid on the Poincare disk, and use real numbers (the (x,y) coordinates of each point), but in practice that would raise all sorts of precision issues that could surely be avoided if one had a proper symbolic coordinate system. You shouldn't need real numbers if you're staying on grid points!

Just like (2,3)+(0,1) is trivial to do by hand (or in your head) for the square grid, we'd like some form of symbolic coordinates (i.e. consisting of finite sequences of symbols) for a hyperbolic grid, in which simple operations on small grid vectors are similarly easy.

If you take some sequence of left and right turns in a hyperbolic grid city, what should you keep track of in your head so you can take the optimal route back to your starting point? In a Euclidean square grid, it is {(int)X, (int)Y, (enum)direction you are facing}, and we all know how to use this. Is there any hyperbolic grid where this question has a nice answer?

Original Question

If we consider the Euclidean plane, then a square grid works well with using two integers (the coordinates) as a representation for vectors that lie on the grid.

Does anybody know of a similarly nice representation for working in the hyperbolic plane?

Desirable features of any such system:
$-$ It should be easy to add two vectors.
$-$ It should be easy to see if two vectors are the same.
$-$ It should be easy to see if two vectors are close.
$-$ It should be easy to rotate a vector by an angle that is a symmetry of the grid.
$-$ Every point in the plane should be near some vector. (The grid shouldn't have large empty regions.)

Note that "addition" using continuous coordinates would most naturally be defined in terms of parallel transport, and it is neither commutative nor associative. On a grid, however, the issue of orientation needs to be addressed differently, since parallel transport along arbitrary grid vectors will introduce rotations that are not a symmetry of the grid, so to remain on the grid, addition will need to be defined using something other than parallel transport.

Since hyperbolic grids have an exponential number of points (as a function of distance from the origin), our symbolic coordinates will need to have a length proportional to the length of the vector.

Don Hatch has a web page which gives some possible grids.

("Easy" means an efficient algorithm that is doable by hand, like how the algorithms for addition and subtraction using the standard digit-sequence representation of integers can be used for the Euclidean square grid. Using hyperbolic functions of real numbers, always keeping track of enough digits to identify the nearest grid point, does not count as easy!)

Many readers seem to be disturbed by a little voice saying "But vectors don't make sense in the hyperbolic plane!": What that voice is really saying is that the hyperbolic plane doesn't give you all the nice properties you are used to in Euclidean space or in vector spaces. So if you define vectors as objects having specific properties you are used to (such as having a direction that is unaffected by parallel transport), then that definition may not correspond to anything in the hyperbolic world. You could use the term isometry, but that is typically a fixed mapping from the space to itself, and in the hyperbolic plane the isometry corresponding to a vector would depend on the starting point. (However, isometries will be central to any solution, I assume.) And a geodesic is a fixed path within the space, no different from a hyperbolic line or segment. The paper "What is a vector in hyperbolic geometry?" offers one solution. Gyrovectors offer another. I deliberately leave them undefined in this question, as I am looking for any workable system.

• I don't think the hyperbolic plane really admits such a grid in the same way that the Euclidean plane does. The Euclidean plane is a Lie group on the nose, but the hyperbolic plane isn't, so it doesn't have an obvious notion of discrete subgroup analogous to vectors with integer coordinates. – Qiaochu Yuan Nov 26 '11 at 16:52
• @Qiaochu: I don't know much about Lie groups, but aren't all the hyperbolic grids essentially examples of discrete subgroups of the group of isometries of the hyperbolic plane? – Matt Nov 26 '11 at 17:34
• Strictly speaking, these are orbits of the action of discrete subgroups, not the discrete subgroups themselves. And I wouldn't call their points "vectors." – Qiaochu Yuan Nov 26 '11 at 17:50
• @Qiaochu: Ok, strictly speaking, I suppose I meant the subgroup of isometries which map the grid onto itself. And your orbit view makes sense too. But back to your first comment, which I didn't understand -- are you suggesting that there is some reason why this question won't have an answer? – Matt Nov 26 '11 at 18:16
• I just think it's strange to use the word "vector" when you don't expect addition to be commutative. – Qiaochu Yuan Nov 26 '11 at 19:32

# Where concepts break

There is no such thing as a parallel transport isometry in hyperbolic geometry. You can have a translation along a geodesic axis, but points off that axis will be transported along a curve. The curve has constant distance to the axis, but is itself not a geodesic. Therefore, your concept of a vector as a combination of length and direction won't translate to the hyperbolic plane.

# Transformations as building blocks

The other formulation you use in that comment, “what takes you from A to B”, is more readily applicable. You can think of vectors as prepresentants for specific isometries, and you can think of the grid points as the oribit of a given point under these isometries. You can come up with isometries of the hyperbolic plane which yield similar results. Instead of a vector you'd describe this class the way you'd describe an arbitrary isometry of the hyperbolic plane. How you do that very much depends on preferences and the model you employ, but for the Poincaré disc model you'd probably use 4 complex numbers to describe a Möbius transformation. You can reduce this to 4 real numbers by using the upper half plane, or by expliting the specific class of possible Möbius transformations, and perhaps even 3 numbers only if you dehomogenize in some way. Expressed in $\mathbb{CP}^1$, the complex projective line, concatenation of Möbius transformations is simply a multiplication of matrices, so that's what would become of your vector addition.

# Congruent polygons

Or you can think of integer grid in the Euclidean plane as a grid made up from squares, and generalize that. In general you have regular $m$-gons, and at each corner $n$ of them meet. Take $2m+2n<mn$ and you are in hyperbolic geometry. The numbers $m$ and $n$ define all the angles and therefore all the lengths as well, as there isn't a global scaling isometry in hyperbolic geometry either. This paragraph will give you a good intuition as to what grids can look like, while the paragraph before this gives you an idea of how to do computations. Together I believe these two concepts should give you as good a toolbox as you can hope for, given the nature of the question and the time it has remained unanswered.

# Representation as a group

Here is something I do in practice: take the polygons described above, and split them along their axes of symmetry to obtain elementary right triangles. Now you can take a single of these triangles, label its edges $a$, $b$ and $c$, and obtain any triangle from your tessalation using a combination of these reflections (see my current avatar). This corresponds to a finitely presented group: $$\left<a,b,c\;\middle|\;1=a^2=b^2=c^2=(ab)^2=(bc)^m=(ca)^n\right>$$ After that, you can do computations in that group. The problem of comparing two labels corresponds to the word problem in this group, which can in fact be solved by computing a canonical form using a deterministic finite state automaton obtained from a string rewrite system by applying the Knuth-Bendix procedure. There might be a slight modification required if you want to label vertices instead of triangles, but in general this approach should work for the tessalations you referred to (i.e. those by Don Hatch). I'm writing up large portions of this as part of my PhD, so I'll likely post a follow-up on this one day.

• "Where concepts break": All true, except that having a length and direction from A to B certainly makes sense in the hyperbolic plane. If you are at A, you can easily point in the direction of B and state the distance to B. What you don't have is "compass directions" that can be defined at every point so that a compass needle can be carried by parallel transport. In contrast to Euclidean directions, hyperbolic directions are best thought of as being associated with the place you are pointing from, or with the line you are pointing along. – Matt Dec 14 '12 at 22:07
• "Transformations as building blocks": All true, but the question is asking for symbolic coordinates for a grid, not continuous coordinates (which don't need a grid). If you really wanted to do calculations via Möbius transformations, you would need to keep track of lots of digits (how many?), and even the matrix multiplication approach starts taking a lot of time due to the digits. My "fishy" answer (and presumably your Knuth-Bendix -> canonical form approach) show that there are solutions taking only linear time in the lengths of the vectors involved. – Matt Dec 14 '12 at 22:08
• "Congruent polygons": All true. Regarding intuition as to what grids can look like, I think actually seeing possible grids is also a pretty good way, as in the link in the original question. I think your new next paragraph gives an even better toolbox! – Matt Dec 14 '12 at 22:08
• "Representation as a group": Nice avatar! Yes, I am asking if any of these groups has a nice canonical form. You appear to be asserting that the Knuth-Bendix procedure will succeed. What do you use as the ordering? Do you have a reduction order for words in your representation? A canonical form can be obtained by shortening the word wherever the path of triangles has high curvature, and then using symmetry-breaking preferences to choose between low-curvature options. My ugly solutions are of this form. Do the methods you refer to ever yield a nice describable solution? – Matt Dec 14 '12 at 22:08
• I'm using ShortLex ordering with $a<b<c$. Which breaks symmetry as well, so the canonical forms don't follow a particularly “nice” pattern. – MvG Dec 15 '12 at 15:58

Here's an example of an answer, inspired by the yellow fish of Escher's "Circle Limit III".
(This one has many nice properties, but I imagine (and hope) that much simpler answers exist.)

Vectors that let you move from grid point to grid point

We will define a vector as the motion taking you from your current yellow fish to some other yellow fish (for example, the one in front of you, or the one in front of the one touching your right-hand fin, etc.). The vector describes a motion to be taken with respect to your current position.

Adding two vectors is straightforward: Do one motion, and then the other. As noted in the original question, vector addition cannot be based on parallel transport of the second vector, and indeed, when you get to the fish at the end of your first vector, you will need to rotate so as to be facing in the fish's direction before starting your second vector.

In this solution, vectors are essentially isometries. Or, to avoid the need for a distinguished "origin", and to allow vectors to be used anywhere, we can think of vectors as equivalence classes on ordered pairs of hyperbolic rays under the relation $\sim$ where $(\vec{A},\vec{B})\sim(\vec{C},\vec{D})$ iff there is an isometry taking $(\vec{A},\vec{B})$ to $(\vec{C},\vec{D})$. For the yellow fish grid, we limit ourselves to rays which start at a yellow fish and extend forward in the fish's direction.

It is clear what it means to add and subtract these vectors. But we still need a symbolic representation for them, with addition and subtraction algorithms.

Representation (part 1)

We will use integers to represent half-fish steps in the forward direction, and a comma to represent jumping to the right (if you are at a fish center, where vectors must start and end) or to the left (if you are at a fish nose, jumping diagonally across the white square) to the neighboring yellow fish chain (which always goes the opposite direction). So (3,2,5) means 3 half-fish-steps forwards, a jump (and about-face) to the left, 2 half-fish-steps forwards, another jump to the left, and finally 5 half-fish-steps forwards.

It is of course possible to define this in a less fishy way: Use a grid of two types ("colors") of points, $+$ (formerly known as fish centers) and $-$ (formerly known as fish noses). These points (when shifted slightly from the Escher arrangement) are the points of the (9,3) grid, colored in the unique way such that every nonagon is either $++-++-++-$ or $--+--+--+$. Each vertex also has a direction (a preferred neighbor), formerly given by the direction of the original chain of yellow fish. We can now define this preferred direction as being the next counter-clockwise neighbor from a $+$ vertex's single $+$ neighbor, or the next clockwise neighbor from a $-$ vertex's single $-$ neighbor.

A "half fish step forwards" is now simply a move to the preferred neighbor, and when we "jump" from one yellow fish chain to a neighboring one, we are simply taking the unique edge in the (9,3) grid that takes us to another vertex of the same color. The remaining neighbor is reached by a "half fish step backwards" (-1).

Note that the sum of the integers in our representation must be even, because we start and end at a fish center (a $+$ vertex). (Otherwise adding two vectors might take you off the grid.)

Operations

Now, how can we use this representation? First of all, to negate a vector, we simply negate all the integers and reverse the sequence.

To add vectors, we simply concatenate them. Do not insert a comma -- where two integers appear next to each other, simply add them together.

Examples:
$(3,2,5) + (4,2) = (3,2,9,2)$
$(3,2,5) - (4,2) = (3,2,5) + (-2,-4) = (3,2,3,-4)$

The only easy rotation is negation. (So we are only getting half the rotations we had on the Euclidean square grid.) If you have a big vector, you can get something close to a rotation of it by left-adding your favorite little vector so that your big vector starts in the direction of your favorite nearby yellow fish. (This method gives us many more possible angles than we had on the square grid, but with reduced accuracy, even if you try to correct the final position with a little vector.)

Jumping on and off Trees (representation, part 2)

In preparation for our canonical form, we will include the tree-shaped regions between yellow fish chains in our representation. By tree, we mean an infinite 3-regular tree graph.

The tree to the right of a fish chain (we only ever consider yellow ones) has vertices in triangle centers connected by edges crossing the neighboring squares. We'll call this a thin tree.

The tree to the left of a fish chain has vertices where three non-yellow fish noses meet, with edges diagonally crossing the incident squares. We'll call this a fat tree.

In the nonagon formulation, the tree vertices are exactly the nonagon centers, and edges connect vertices when their nonagons are adjacent and of the same type. Nonagons of the $++-++-++-$ type are "thin" nonagons, while nonagons of the $--+--+--+$ type are "fat" nonagons (even though they are now the same size and shape, unlike in the fish picture). Tree edges and monochromatic nonagon edges are perpendicular bisectors of each other, again, $+$ for thin and $-$ for fat.

We will use $^\prime$ to indicate jumping onto a tree, and $^\backprime$ to indicate jumping off. (Recall that a comma indicates jumping across a tree.) When on a tree, we are always on an edge, facing in the direction of travel. From a fish center, we jump left onto the fat tree. From a fish nose, we jump right onto the thin tree. In either case, we jump onto the edge leaving the nearby tree vertex, facing away from our fish chain. Jumping off works the same way, moving forwards onto a fish chain. Note that jumping onto a tree and off again gets you to a different fish chain (a farther one than a comma takes you to). Note also that a comma jump and a $^\prime$$^\backprime jump go in opposite directions, starting from the same jump-off point. While on the tree, we use the symbols L and R to indicate moving forwards onto one of the two edges we are facing. On a thin tree (a + tree), L means a left turn and R means a right turn. On a fat tree (a - tree), this is reversed, so R means left and L means right. Finally, we also use the symbol U to indicate an about-face while on a tree. That is, we stay on the same edge of the tree but reverse our direction. As an example of using tree travel, you can see (by tracing it out on Escher's fish picture) that the path 2,1^\prime L^\backprime 1,4,2 is a roundtrip from a yellow fish to itself. Canonical Form The reason for adding tree travel to our vector representation is that it allows for a mathematically pleasing canonical form. The overall form of a vector is an alternation between fish chains (which we will call "roads" here, since they let us travel back and forth on them) and trees. (Think of a comma jump as being onto the intervening tree and then off onto the next road.) Every road is a line that cuts the plane in half. Every road is bordered by two trees, while every tree is bordered by infinitely many roads. We start and end on a road. Every other road either separates the starting point from the ending point or does not. If it does not (and it is not our starting or ending road), and our route crosses the road, then it will have to cross back, back onto the very same tree it was on before! So to begin with, our canonical form will minimize the number of road-tree jumps in the route. This means that in addition to the starting and ending roads, it will use exactly those roads which separate the starting point from the ending point, crossing (and possibly driving along) each such road exactly once. This fixes the sequence of roads and trees to a single canonical sequence. All that remains is to determine the jumping points onto and off of the trees. To fix the route taken in a tree, we specify that it should be the shortest possible route. Consider a tree that is being used to get from road A to road B. If it is possible to get from A to B with a comma jump, then we say that A and B are "close". For close roads, the comma jump should be used, and there is only one place it can be used. Otherwise, the shortest distance between A and B is at least that of a ^\prime$$^\backprime$ jump, and we say that A and B are "far". In this case, the next paragraph will show that the shortest route through the tree is unique.

Given a tree $T$ and adjacent road A, define the bank of A to be the infinite path of edges and vertices in $T$ that runs alongside the road A. Now, if we want to get from road A to road B through the intervening tree $T$ (that is, without using any other roads or trees), and A and B are far, then we can see that we will have to use the edges in path $P$, where $P$ is the (unique) shortest path in $T$ from the bank of A to the bank of B. For far roads, $P$ has length at least 1. Fortunately, we can perform a $^\prime$ jump from A directly onto $P$, continue on $P$ to its last edge, and then do a $^\backprime$ jump directly onto B. This gives a uniquely defined tree route to be taken from A to B. (For far roads, that is -- for near roads, the banks will share an edge, and a comma jump should be used there.)

Symbolic Calculations

We can manipulate our vector expressions using symbolic equivalences.

The following axioms suffice: $$\begin{eqnarray} (1) & ~~~~~~~ & UU & = & \emptyset & ~~~~~ & \mbox{turns are}~180^\circ \\ (2) & & RURURU & = & \emptyset & & \mbox{vertices are degree 3} \\ (3) & & RULU & = & \emptyset & & \mbox{left is the opposite of right} \\ (4) & & {}^\backprime {}^\prime & = & U & & \mbox{jumping off and on gets back to the same tree} \\ (5) & & {}^\prime URRU {}^\backprime & = & 2 & & \mbox{relating road distance to tree steps} \\ (6) & & \mbox{adjacent integers} & = & \mbox{their sum} & & \mbox{road travel is a number line} \\ \end{eqnarray}$$

We use $\emptyset$ to indicate the empty string, a length-zero sequence of moves. The comma is absent from these axioms; it will be defined below in terms of the other symbols.

Our sequences of symbols are essentially a monoid with identity $\emptyset$, but with restrictions:
The tree moves $\{L,R,U\}$ are only allowed to appear between $^\prime$ and $^\backprime$, and only the tree moves are allowed to appear there. Integers (indicating road travel) and commas can only appear at the beginning or end of a vector, or between $^\backprime$ and $^\prime$. The symbols $^\prime$ and $^\backprime$ must alternate, and if they appear at all in a complete vector, $^\prime$ must be the first and $^\backprime$ must be the last.

The first three axioms are for paths within a tree. From those we can prove the following: $$\begin{eqnarray} URURUR & = & \emptyset \\ LULULU & = & \emptyset \\ ULULUL & = & \emptyset \\ LURU & = & \emptyset \\ URUL & = & \emptyset \\ ULUR & = & \emptyset \\ LUR & = & U & ~~~~~ & \mbox{U-reduction} \\ RUL & = & U & & \mbox{U-reduction} \\ RUR & = & L & & \mbox{U-reduction} \\ LUL & = & R & & \mbox{U-reduction} \\ \end{eqnarray}$$

We refer to the last four of those as "U-reductions".

The remaining axioms regard jumping between roads and trees, and traveling on roads. (Note that axiom 5 is why we needed to reverse the sense of $R$ and $L$ on fat trees.) They allow us to prove the following: $$\begin{eqnarray} 2^k & = & {}^\prime URL^{k-1}RU {}^\backprime & ~~~ & \mbox{note: 2^k means k consecutive 2s, equivalent by} \\ & & & & ~~~~~~~~~~ \mbox{axiom 6 to the single integer: (2 times k)} \\ {}^\prime U {}^\backprime & = & \emptyset & & \mbox{U-reduction} \\ {}^\prime ULLU {}^\backprime & = & -2 \\ {}^\backprime 2 {}^\prime & = & RR \\ (-2)^k & = & {}^\prime ULR^{k-1}LU {}^\backprime \\ {}^\backprime 2^k {}^\prime & = & RL^{k-1}R & & \mbox{even number reduction} \\ {}^\backprime (-2)^k {}^\prime & = & LR^{k-1}L & & \mbox{even number reduction} \\ {}^\prime URR & = & 2^\prime & & \mbox{U-reduction} \\ {}^\prime URL & = & 2^\prime UR & & \mbox{U-reduction} \\ {}^\prime ULR & = & -2^\prime UL & & \mbox{U-reduction} \\ {}^\prime ULL & = & -2^\prime & & \mbox{U-reduction} \\ LLU{}^\backprime & = & {}^\backprime -2 & & \mbox{U-reduction} \\ RLU{}^\backprime & = & LU{}^\backprime -2 & & \mbox{U-reduction} \\ LRU{}^\backprime & = & RU{}^\backprime -2 & & \mbox{U-reduction} \\ RRU{}^\backprime & = & {}^\backprime -2 & & \mbox{U-reduction} \\ \end{eqnarray}$$

Finally, we define the comma: $$\begin{eqnarray} (7) & ~~~~~~~~~~ & , & = & 1 {}^\prime URU {}^\backprime 1 \\ & & & = & -1 {}^\prime ULU {}^\backprime -1 \\ & & & = & 1 {}^\prime LU {}^\backprime 3 \\ & & & = & 3 {}^\prime UL {}^\backprime 1 \\ & & & = & -1 {}^\prime RU {}^\backprime -3 \\ & & & = & -3 {}^\prime UR {}^\backprime -1 \\ \end{eqnarray}$$

We refer to these as the comma forms. (The first line is the axiomatic definition of the comma, from which the remaining forms may be derived.)

It is also possible to prove some basic comma identities: $$\begin{eqnarray} ,, & = & \emptyset \\ 2,2,2, & = & \emptyset \\ \end{eqnarray}$$

To add two vectors, concatenate them (and canonicalize if desired). To subtract, add the negation.

To negate a vector (or any subsequence of symbols), simply (1) reverse the sequence, (2) swap $L$ with $R$ everywhere, (3) swap $^\prime$ with $^\backprime$ everywhere, and (4) add a $U$ to any end (beginning or end) of the sequence where tree moves are allowed (this step is not relevant to complete vectors, since they don't start or end with tree moves).

To prove that this negation method always yields an inverse, just find inverses for each of the symbols (thereby showing that our restricted monoid is in fact a restricted group). If we just consider complete vector sequences, they form an ordinary group, of course: the group of isometries that map yellow fish to yellow fish. If we lift the restrictions and simply consider each symbol as an isometry, then we also get a group, but it doesn't stay on any grid.

Calculating the Canonical Form

The canonical form is easily specified as having no $U$ symbols, having all adjacent integers summed, and having only odd integers between $^\backprime$ and $^\prime$ (expand any commas when checking the parity).

To convert a vector to canonical form, start with its full path, with the commas expanded, and do the following as long as possible:
$\bullet~~~~~$ Even number reduction
$\bullet~~~~~$ U-reduction (always shortens the sequence length)
When neither of those is possible any longer, then all interior numbers are odd, and all tree paths are either U-free or reducible to a comma via one of the comma forms. Reduce these to commas where possible.

This yields the canonical form. Its calculation takes only linear time in the length of the vector.

Applicability to Other Grids

The road/tree decomposition of the nonagon grid can also be done with other grids. For example, Escher's fish have positions precisely related to the octagonal grid whose edges are exactly the segments connecting the vertices of Escher's triangles to their centers. If we select a set of vertices $S$ of the (8,3) grid such that each octagon touches exactly two of them, diametrically opposed across the octagon, then the vertices of $S$ can be used as exactly the vertices of the trees, with the edges being the octagon diameters between them. So we can also have a non-fishy development of the road/tree structure based on the (8,3) grid.

Does this mean that the octagon grid and the nonagon grid fit nicely on top of each other? No, the nonagon trees have longer edges than the octagon trees, and the roads are closer together. This is an instance of a general transformation we can do to get from one tree/road structure to another. If we define a tree/road structure as having $120^\circ$ symmetry at tree vertices, and glide reflection symmetry across roads (with the same amount of glide in either direction), then one degree of freedom remains (the edge length, which is bounded from below (so that banks don't close in on themselves) but not from above), and by adjusting this scalar parameter we can fit the structure to a variety of grids. For example, the (4,6) grid, in which 6 squares meet at every corner, can use trees whose edges are diagonals of the squares. Many other grids can also have a tree/road structure mapped onto them in a regular way, and the coordinates developed above can be used for all such grids.

Finally, we note that the geometric length of a vector can be approximated by the symbol length of its canonical form, where integers contribute their absolute value. This length will be within a constant factor of the true geometric length. The factor will depend on which grid is being used. This is similar to estimating the length of a Euclidean $(x,y)$ vector as $x+y$, which also gives a result that is within a constant factor of the true geometric length.

• TL;DR. This might be irrelevant to your approach, but note that the white lines in that Escher image are not geodesics!. They are curved even according to the hyperbolic metric. So the axis of the translation is slightly to the left of the yellow fishes. – MvG Dec 10 '12 at 16:35
• @MvG: Absolutely correct. This is why the fishes appear very close to the same color ones on their right, but far from the ones on their left. If you shift each row of fishes onto the line they are asymptotic to (the one you refer to as the axis of translation), then the left and right distances will match. – Matt Dec 14 '12 at 20:04
• The main motivation for posting this answer is because people seem to be ignoring the question because they assume it makes no sense or cannot have an answer. This answer shows by example that the question is answerable. This answer also presents a pretty clean, symmetric, origin-free way of navigating that works for quite a number of grids (all grids, if you use r-regular instead of 3-regular trees). I have uglier solutions that only work for specific grids, but no really nice simple solution, even for a specific grid. – Matt Dec 14 '12 at 20:20
• I'm assume that lack of answers was in large part due to your use of vocabulary, particularly in the original formulation. Vectors (in the common sense) and vector addition simply won't work. The edit made the question somewhat clearer as you focus on labels for grid points. I edited my own answer with that in mind. – MvG Dec 14 '12 at 21:26

You could use the binary tiling.

In the upper half-plane model, the vertices are points with coordinates $(2^n, m2^n)$ where $n,m \in \mathbb{Z}$. Let $(n,m)$ be our representation. The point represented with $(n,m)$ is connected with $(n,m-1)$, $(n,m+1)$, $(n-1,2m)$, and if $2|m$, $(n+1, m/2)$. Faces could be represented in a similar way.

A hyperbolic city based on this tiling can be navigated very elegantly.

• Binary tilings are not a grid: They only have a single line (x=0) where you can shift the tiling onto itself (by doubling/halving (x,y)), and no rotational symmetries anywhere. For most tiles, the nearest tile that "looks the same" (regarding how the tiling looks from there) is far away (infinitely far, on average). However you are right that a good route between tiles $A$ and $B$ is easy to compute: Two people at $A$ and $B$ each walk straight up, to the lowest row where they are at most 3 tiles away from each other (horizontally), at which point they move horizontally (if necessary) to meet. – Matt Mar 13 '18 at 14:17
• Well, I do not know any established definition of a hyperbolic grid. You asked for a nice answer, and I believe that there are no grids with rotational symmetries and solutions nicer than ones in the other answers. – Zeno Rogue Mar 14 '18 at 10:35
• If you are interested in the problem of computing the distance in a hyperbolic grid algorithmically, our paper deals with this: arxiv.org/abs/1707.01124 (we have a more recent version, but not on ArXiv yet) Your solution for the binary tiling generalizes to regular tilings, but with some complications. – Zeno Rogue Mar 14 '18 at 10:38
• Nice paper! And nice game! The definition of "grid" in the paper is closer to what I would think of as a "triangulation". In the question, I gave a link to a page with pictures of over a hundred grids. A key idea is that, like the (7,3) grid in HyperRogue, a grid (whatever it is) "looks the same" from an infinite number of points (and there exists a real $d$ such that every point in the plane is within distance $d$ of one of these points). This allows the definition of a fundamental polygon, showing that the grid can be described as a tiling. – Matt Mar 18 '18 at 18:53
• The binary tiling is (to me) more reminiscent of aperiodic tilings like the Penrose tiling, where it is commonly the case that any local configuration can indeed be found repeated all over the plane, but for larger local configurations you need to go larger distances to get to the next place with the same configuration. These tilings "look the same up to a distance $s$" from an infinite number of points (covering the plane as before), for any positive real $s$, but not for $s=\infty$. Like the binary tiling, these aperiodic tilings typically have structure with a recursive nested nature. – Matt Mar 18 '18 at 19:01