Deciding multiple tiling by polygons in polynomial time

DOI10.1007/S10998-020-00361-YzbMATH Open1488.52027arXiv1912.01904OpenAlexW3092651939MaRDI QIDQ2043725FDOQ2043725

Mihail N. Kolountzakis

Publication date: 3 August 2021

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

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.

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

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

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)

Cites Work

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

Cited In (7)

• Tiling with Squares and Packing Dominos in Polynomial Time
• Aspects of a multivariate complexity analysis for rectangle tiling
• On the structure of multiple translational tilings by polygonal regions
• A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino
• Characterization of the two-dimensional fivefold and sixfold lattice tiles
• Periodic structure of translational multi-tilings in the plane
• Title not available (Why is that?)

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)