Deciding multiple tiling by polygons in polynomial time (Q2043725)

Consider convex polygons. It is known that only parallelograms and centrally symmetric hexagons admit tilings of the plane by translations. In such a case, almost all points of the plane, except for the boundary points of the tiles, are covered exactly once by tiles. In a multiple tiling almost every point of the plane is covered by the same number of tiles. \par The problem is as follows. Let \(P\) be a centrally symmetric convex polygon in the plane. Decide if \(P\) admits a multiple tiling of the plane by translations from a lattice \(L\). A theorem by \textit{U. Bolle} [in: Intuitive geometry. Proceedings of the 3rd international conference held in Szeged, Hungary, from 2 to 7 September, 1991. Amsterdam: North-Holland; Budapest: János Bolyai Mathemtical Society. 39--43 (1994; Zbl 0818.52016)] gives some conditions on the pairs of parallel sides of \(P\) and the translation vectors of \(L\) when \(P+L\) is a multiple tiling of the plane. \par In the paper under review, the author proposes an algorithm, running in polynomial time in the number of sides of the polygon, which decides if a centrally symmetric convex polygon can multi-tile the plane by translations.