Order-5 square tiling

What is a description of the graph representing the faces of the Order-5 square tiling. Alternatively, this can be seen as the graph of vertices of the its dual, the Order 4 pentagon tiling.

Preferably, it should be a description useful for use with a computer (all that is needed is a way to find the neighbors of any node). The reason why is got interested in using hyperbolic geometry in games, so as a short cut to all the calculus needed I decided I'd make a bunch of rooms corresponding to a tessellation of the hyperbolic plane (and approximate each room as Euclidean).

Also, these description should be discrete (i.e. not rely on real numbers (which would need to be approximated with floating numbers on a computer))?


(Working with groups was too hard, so I decided to use a different approach, taking a leaf out of HyperRogue's book.)

We begin by constructing a spanning tree for the graph. It looks like this, except for being infinite:


Each path from the root to a vertex in the graph is described by an initial step North, East, South, or West, followed by a sequence of steps Forward, Left, or Right. In fact, all paths from the root can be described in this way, but the paths that correspond to to edges of this spanning tree satisfy two further conditions:

  1. You can't take two consecutive steps Right.
  2. You can't take two steps Left without a Right step somewhere in between.

    (Left, Left and Left, Forward, Left, and Left, Forward, Forward, Left and so on are all forbidden.)

In each quarter of the tree, the number of vertices at a given depth appears to be given by sequence A033303 in the OEIS.

To specify a vertex in the graph, we specify the path from the root to that vertex.

Of the four neighbors of a vertex, at least three are neighbors in the tree, and are easy to find. We just take the path specifying our vertex, and do one of:

  • Erase the last step, or
  • Append a Left, Forward, or Right step.

Sometimes, however, we get a non-tree edge in this way: this happens exactly when we take one of the forbidden steps above. In that case, we need to simplify the result to a path that is valid in the tree.

Let $\ell$ be the function that "turns a direction left", mapping North to West, West to South, South to East, East to North, Right to Forward, and Forward to Left; let $r$ be its inverse. (The values $\ell(\text{Left})$ and $r(\text{Right})$ are both undefined.) Then:

  1. The forbidden ending "$\dots, x$, Right, Right" simplifies to the ending "$\dots, r(x)$, Left".
  2. The forbidden ending "$\dots, x$, Left, Left" simplifies to the ending "$\dots, \ell(x)$, Right".
  3. The forbidden ending $\dots, x$, Left, Forward, Left" simplifies to the ending $\dots, \ell(x)$, Right, Forward, Right".
  4. In general, the forbidden ending "$\dots, x$, Left, Forward, ..., Forward, Left" simplifies to the ending "$\dots, \ell(x)$, Right, Forward, ..., Right, Forward, Right", with an equal number of Forward steps as before interleaved with Right steps.
  • $\begingroup$ Fixing the bug in the old version was hard, so here's a different approach to the problem. It makes sense theoretically, and I've checked it experimentally in Mathematica. $\endgroup$ – Misha Lavrov Apr 14 '17 at 1:24
  • $\begingroup$ cool. How does this version generalize? $\endgroup$ – PyRulez Apr 14 '17 at 1:30
  • $\begingroup$ See the HyperRogue link for an example of a spanning tree for a different tiling. (I don't have a general answer for which paths are valid in the tree for an arbitrary tiling, but some tree will probably exist.) $\endgroup$ – Misha Lavrov Apr 14 '17 at 1:33
  • $\begingroup$ Your symmetry approach might work if you use this. $\endgroup$ – PyRulez Aug 11 '17 at 1:43
  • $\begingroup$ Also, could we the Mathematica code? $\endgroup$ – PyRulez Jan 19 '18 at 1:22

You can represent this as the $\Delta(2,4,5)$ Von Dyck group.

In particular, you can generate the group by

  • Rotate left 90 degrees ($L$)
  • Rotate right 90 degrees ($R$)
  • Move forward one cell, and then turn around ($F$)

Given a string of such symbols, we can simplify to a normal form with the following operations:

  • Replace $L^2$ with $R^2$
  • Remove $F^2$
  • Replace $R^3$ with $L$
  • Replace $(FL)^2F$ with $(RF)^2R$
  • Replace $FLFR^2(FL)^2$ with $RF(RFR)^2F$
  • Replace $(FLFR^2)^2$ with $RF(RFR)^2FL$

(generated with sagemath).

Any two representations of the same element in the Von Dyck group will normalize to the same result under these operations.

Finally, note that each element represents both a square, and a direction. Therefore, we will say that two elements represent the same square by ignoring $R$ and $L$ at the beginning of the string.

Two cells are adjacent if you can get from one to the other with zero to three $R$ operations and exactly one $F$ operation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.