Tiling with Squares and Packing Dominos in Polynomial Time
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\times k$ squares for any fixed $k$ (that is, deciding if $P$ is the union of a set of non-overlapping $k\time...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
ACM
2023
|
| Online Access: | https://hdl.handle.net/1721.1/150836 |
| _version_ | 1811088919378264064 |
|---|---|
| author | Aamand, Anders Abrahamsen, Mikkel Ahle, Thomas Rasmussen, Peter |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Aamand, Anders Abrahamsen, Mikkel Ahle, Thomas Rasmussen, Peter |
| author_sort | Aamand, Anders |
| collection | MIT |
| description | 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\times k$ squares for any fixed $k$ (that is, deciding if $P$ is the union of a set of non-overlapping $k\times k$ squares) and for packing $P$ with a maximum number of non-overlapping and axis-parallel $2\times 1$ dominos, allowing rotations by $90^\circ$. As packing is more general than tiling, the latter algorithm can also be used to decide if $P$ can be tiled by $2\times 1$ dominos. These are classical problems with important applications in VLSI design, and the related problem of finding a maximum packing of $2\times 2$ squares is known to be NP-hard [J. Algorithms 1990]. For our 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(n\log 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 problem of packing/tiling with dominos to finding a maximum/perfect matching in a graph with $O(n^3)$ vertices. This leads to algorithms with running times $O(n^3 \frac{\log^3 n}{\log^2\log n})$ and $O(n^3 \frac{\log^2 n}{\log\log n})$, respectively. |
| first_indexed | 2024-09-23T14:10:01Z |
| format | Article |
| id | mit-1721.1/150836 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:10:01Z |
| publishDate | 2023 |
| publisher | ACM |
| record_format | dspace |
| spelling | mit-1721.1/1508362024-01-22T18:24:06Z Tiling with Squares and Packing Dominos in Polynomial Time Aamand, Anders Abrahamsen, Mikkel Ahle, Thomas Rasmussen, Peter Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory 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\times k$ squares for any fixed $k$ (that is, deciding if $P$ is the union of a set of non-overlapping $k\times k$ squares) and for packing $P$ with a maximum number of non-overlapping and axis-parallel $2\times 1$ dominos, allowing rotations by $90^\circ$. As packing is more general than tiling, the latter algorithm can also be used to decide if $P$ can be tiled by $2\times 1$ dominos. These are classical problems with important applications in VLSI design, and the related problem of finding a maximum packing of $2\times 2$ squares is known to be NP-hard [J. Algorithms 1990]. For our 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(n\log 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 problem of packing/tiling with dominos to finding a maximum/perfect matching in a graph with $O(n^3)$ vertices. This leads to algorithms with running times $O(n^3 \frac{\log^3 n}{\log^2\log n})$ and $O(n^3 \frac{\log^2 n}{\log\log n})$, respectively. 2023-06-01T19:59:43Z 2023-06-01T19:59:43Z 2023-06-01T07:45:10Z Article http://purl.org/eprint/type/JournalArticle 1549-6325 https://hdl.handle.net/1721.1/150836 Aamand, Anders, Abrahamsen, Mikkel, Ahle, Thomas and Rasmussen, Peter. "Tiling with Squares and Packing Dominos in Polynomial Time." ACM Transactions on Algorithms. PUBLISHER_CC en http://dx.doi.org/10.1145/3597932 ACM Transactions on Algorithms Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The author(s) application/pdf ACM Association for Computing Machinery |
| spellingShingle | Aamand, Anders Abrahamsen, Mikkel Ahle, Thomas Rasmussen, Peter Tiling with Squares and Packing Dominos in Polynomial Time |
| title | Tiling with Squares and Packing Dominos in Polynomial Time |
| title_full | Tiling with Squares and Packing Dominos in Polynomial Time |
| title_fullStr | Tiling with Squares and Packing Dominos in Polynomial Time |
| title_full_unstemmed | Tiling with Squares and Packing Dominos in Polynomial Time |
| title_short | Tiling with Squares and Packing Dominos in Polynomial Time |
| title_sort | tiling with squares and packing dominos in polynomial time |
| url | https://hdl.handle.net/1721.1/150836 |
| work_keys_str_mv | AT aamandanders tilingwithsquaresandpackingdominosinpolynomialtime AT abrahamsenmikkel tilingwithsquaresandpackingdominosinpolynomialtime AT ahlethomas tilingwithsquaresandpackingdominosinpolynomialtime AT rasmussenpeter tilingwithsquaresandpackingdominosinpolynomialtime |