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.

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)