Symbolic coordinates for a hyperbolic grid?

Solution 1:

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.

Solution 2:

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.

Solution 3:

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.