## 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(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 problems of packing and tiling with dominos to finding a maximum and perfect matching in a graph with O(n^{3}) vertices. This leads to algorithms with running times O(n^{3}_{log}^{log}_{2 log}^{3 n}_{n} ) and O(n^{3}_{log}^{log}_{log}^{2 n}_{n} ), respectively.

Original language | English |
---|---|

Title of host publication | 38th International Symposium on Computational Geometry, SoCG 2022 |

Editors | Xavier Goaoc, Michael Kerber |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Publication date | 2022 |

Article number | 1 |

ISBN (Electronic) | 9783959772273 |

DOIs | |

Publication status | Published - 2022 |

Event | 38th International Symposium on Computational Geometry, SoCG 2022 - Berlin, Germany Duration: 7 Jun 2022 → 10 Jun 2022 |

### Conference

Conference | 38th International Symposium on Computational Geometry, SoCG 2022 |
---|---|

Country/Territory | Germany |

City | Berlin |

Period | 07/06/2022 → 10/06/2022 |

Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 224 |

ISSN | 1868-8969 |

### Bibliographical note

Publisher Copyright:© Anders Aamand, Mikkel Abrahamsen, Thomas Ahle, and Peter M. R. Rasmussen; licensed under Creative Commons License CC-BY 4.0

## Keywords

- packing
- polyominos
- tiling