Deciding multiple tiling by polygons in polynomial time
- PDF / 301,553 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 83 Downloads / 171 Views
Deciding multiple tiling by polygons in polynomial time Mihail N. Kolountzakis1
© Akadémiai Kiadó, Budapest, Hungary 2020
Abstract Suppose P is a symmetric convex polygon in the plane. We give an algorithm, running in polynomial time in the number of sides of the polygon, which decides if P can tile the plane by translations 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, . . . , n one of two given vectors e j or τ j so that the selection spans a discrete additive subgroup. Keywords Lattices · Tiling · Algorithms · Discrete subgroups Mathematics Subject Classification Primary 52C05; Secondary 68Q25 · 52C20 · 52B55 · 11H31
1 Multiple tiling by translations with a single tile In this note we are discussing when a convex polygon can tile the plane by translations with a lattice. A lattice in the plane is a discrete additive subgroup which contains two linearly independent vectors. Equivalently a lattice L ⊆ R2 is a linear image of Z2 , L = AZd , where the matrix A is non-singular. If P is a convex polygon and L is any subset of the plane then we say that P tiles by translations with L if the translates P + , ( ∈ L), cover almost every point of the plane (in the sense of Lebesgue measure) exactly once. For instance, if P = [0, 1]2 is the unit square and L = Z2 then we do indeed have tiling by translations. In this case the only points of the plane that are not covered exactly once by the copies of P are the points on the boundaries of these copies, clearly a set of Lebesgue measure zero.
B 1
Mihail N. Kolountzakis [email protected] Department of Mathematics and Applied Mathematics, University of Crete, Voutes Campus, 70013 Heraklion, Crete, Greece
123
M. N. Kolountzakis Fig. 1 A polygonal domain with the pairing property. It is easy to see that it tiles with a lattice at level 1
If we restrict ourselves to P being a convex polygon it has long been known that P has to be symmetric in order to be able to tile the plane. It is also known that only parallelograms and symmetric hexagons admit tilings. The problem becomes more interesting if one considers multiple tilings, i.e., tilings at higher level than 1: almost every point of the plane is covered the same number of times by the translates of P. This number is called the level of the tiling. In this case many more convex polygons (again, they must be symmetric) admit multiple tilings. For instance, every symmetric convex polygon whose vertices have rational coordinates admits multiple tiling by the lattice Zd at some level (this is easily seen from Theorem 1.1 below). It was Bolle [1] who first studied the question “when does a polygon tile multiply with a given lattice”. Bolle’s characterization is the following as was modified in [4]. Theorem 1.1 Let P be a convex polygon in R2 , and L be a lattice in R2 . Then P + L is a tiling of the plane at some level if and only if P is centrally symmetric, and for each pair of par
Data Loading...
