License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2022.1
URN: urn:nbn:de:0030-drops-160096
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16009/
Aamand, Anders ;
Abrahamsen, Mikkel ;
Ahle, Thomas ;
Rasmussen, Peter M. R.
Tiling with Squares and Packing Dominos in Polynomial Time
Abstract
A polyomino is a polygonal region with axis-parallel edges and corners of integral coordinates, which may have holes. In this paper, we consider planar tiling and packing problems with polyomino pieces and a polyomino container P. We give polynomial-time algorithms for deciding if P can be tiled with k× k squares for any fixed k which can be part of the input (that is, deciding if P is the union of a set of non-overlapping k× k squares) and for packing P with a maximum number of non-overlapping and axis-parallel 2× 1 dominos, allowing rotations by 90^∘. As packing is more general than tiling, the latter algorithm can also be used to decide if P can be tiled by 2× 1 dominos.
These are classical problems with important applications in VLSI design, and the related problem of finding a maximum packing of 2× 2 squares is known to be NP-hard [J. Algorithms 1990]. For our three problems there are known pseudo-polynomial-time algorithms, that is, algorithms with running times polynomial in the area or perimeter of P. However, the standard, compact way to represent a polygon is by listing the coordinates of the corners in binary. We use this representation, and thus present the first polynomial-time algorithms for the problems. Concretely, we give a simple O(nlog n)-time algorithm for tiling with squares, where n is the number of corners of P. We then give a more involved algorithm that reduces the problems of packing and tiling with dominos to finding a maximum and perfect matching in a graph with O(n³) vertices. This leads to algorithms with running times O(n³(log³ n)/(log²log n)) and O(n³(log² n)/(log log n)), respectively.
BibTeX - Entry
@InProceedings{aamand_et_al:LIPIcs.SoCG.2022.1,
author = {Aamand, Anders and Abrahamsen, Mikkel and Ahle, Thomas and Rasmussen, Peter M. R.},
title = {{Tiling with Squares and Packing Dominos in Polynomial Time}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {1:1--1:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-227-3},
ISSN = {1868-8969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16009},
URN = {urn:nbn:de:0030-drops-160096},
doi = {10.4230/LIPIcs.SoCG.2022.1},
annote = {Keywords: packing, tiling, polyominos}
}
|
Keywords: |
|
packing, tiling, polyominos |
|
Collection: |
|
38th International Symposium on Computational Geometry (SoCG 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
01.06.2022 |
