Deciding multiple tiling by polygons in polynomial time

DOI10.1007/S10998-020-00361-YMaRDI QIDQ2043725zbMATH OpenOpenAlexFDO

Authors Mihail N. Kolountzakis

Publication date 3 August 2021

Published in Periodica Mathematica Hungarica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.01904

zbMATH Keywords

algorithmscentrally symmetric convex polygondiscrete subgroupslatticestiling by translations

Mathematics Subject Classification ID

Lattice packing and covering (number-theoretic aspects) (11H31) Computational aspects related to convexity (52B55) Lattices and convex bodies in (2) dimensions (aspects of discrete geometry) (52C05) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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 $a{u}_j$ so that the selection spans a discrete additive subgroup.

Review text

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.

Recommendations

• Periodic structure of translational multi-tilings in the plane
• Translational tilings by a polytope, with multiplicity
• scientific article; zbMATH DE number 17705
• scientific article; zbMATH DE number 4023310
• An optimal algorithm for tiling the plane with a translated polyomino
• Tiling a polygon with parallelograms
• Polyomino convolutions and tiling problems
• A parallelogram tile fills the plane by translation in at most two distinct ways
• Multi-tiling and equidecomposability of polytopes by lattice translates
• On translating one polyomino to tile the plane

Cites work

• Modern computer algebra
• Multi-tiling and equidecomposability of polytopes by lattice translates
• On the structure of multiple translational tilings by polygonal regions
• Structure results for multiple tilings in 3D
• Translational tilings by a polytope, with multiplicity

Cited in

(10)

• On the structure of multiple translational tilings by polygonal regions
• Tiling a polygon with parallelograms
• Translational tilings by a polytope, with multiplicity
• A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino
• Aspects of a multivariate complexity analysis for rectangle tiling
• scientific article; zbMATH DE number 739010 (Why is no real title available?)
• Periodic structure of translational multi-tilings in the plane
• Multi-tiling and equidecomposability of polytopes by lattice translates
• Tiling with Squares and Packing Dominos in Polynomial Time
• Characterization of the two-dimensional fivefold and sixfold lattice tiles

This page was built for publication: Deciding multiple tiling by polygons in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2043725)