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

algorithmslatticesdiscrete subgroupscentrally symmetric convex polygontiling by translations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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) Lattice packing and covering (number-theoretic aspects) (11H31)

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.

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

(9)

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

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)