No label defined (Q4946211)

Given a bounded \textit{figure} (i.e., a patch, possibly with holes) from the regular tiling of the hyperbolic plane by (regular) \(4g\)-gons, and bars whose length~\(v_i\) depends on the orientation (\(i=1,\dots,g\), for each of the \(g\)~different directions). Can the figure be tiled with bars from this set? The analoguous problem in the Euclidean plane (figures on the regular square tiling) is known to be NP-complete in the general case (Robson, 1991) if the length of either the horizontal or the vertical bars is at least~3, and solvable in polynomial time for patches without holes (Kenyon and Kenyon), or (with holes) if both the horizontal and the vertical bars have length~2. In contrast to that, it turns out that the hyperbolic version can always be solved in polynomial time. Moreover, the tiling, if it exists, is uniquely determined. The algorithm uses a group-theoretic description of the figure (a word with \(2g\)~letters, equivalent to the boundary of the figure, representing the Cayley complex of a surface) and is the generalization of a method used by Dehn (1911) to solve the word problem for certain surface groups. For the entire collection see [Zbl 0930.00042].