math.MG math.CO math.NT
Deciding multiple tiling by polygons in polynomial time. Suppose P is a symmetric convex polygon in the plane. We give a polynomial time algorithm that decides if P can tile the plane by transations at some level (not necessarily at level one this is multiple tiling). The main technical contribution is a polynomial time algorithm that selects, if this is possible, for each j 1,2, ldots,n one of two given vectors e j or tau j so that the selection spans a discrete additive subgroup.