Document Open Access Logo

Tiling with Squares and Packing Dominos in Polynomial Time

Authors Anders Aamand , Mikkel Abrahamsen , Thomas Ahle , Peter M. R. Rasmussen

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.1.pdf
  • Filesize: 1.13 MB
  • 17 pages

Document Identifiers

Author Details

Anders Aamand
  • MIT, Cambridge, MA, US
Mikkel Abrahamsen
  • BARC, University of Copenhagen, Denmark
Thomas Ahle
  • BARC, University of Copenhagen, Denmark
Peter M. R. Rasmussen
  • BARC, University of Copenhagen, Denmark

Funding

  • Aamand, Anders: Supported by a DFF-International Postdoc Grant from the Independent Research Fund Denmark.
  • Abrahamsen, Mikkel: Supported by Starting Grant 1054-00032B from the Independent Research Fund Denmark under the Sapere Aude research career programme. BARC is supported by the VILLUM Foundation grant 16582.
  • Ahle, Thomas: BARC is supported by the VILLUM Foundation grant 16582.
  • Rasmussen, Peter M. R.: BARC is supported by the VILLUM Foundation grant 16582.

Cite As Get BibTex

Anders Aamand, Mikkel Abrahamsen, Thomas Ahle, and Peter M. R. Rasmussen. Tiling with Squares and Packing Dominos in Polynomial Time. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 1:1-1:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SoCG.2022.1

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • packing
  • tiling
  • polyominos

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Danièle Beauquier and Maurice Nivat. On translating one polyomino to tile the plane. Discrete & Computational Geometry, 6:575-592, 1991. URL: https://doi.org/10.1007/BF02574705.
  2. Danièle Beauquier, Maurice Nivat, Eric Remila, and Mike Robson. Tiling figures of the plane with two bars. Computational Geometry, 5(1):1-25, 1995. URL: https://doi.org/10.1016/0925-7721(94)00015-N.
  3. Robert Berger. The undecidability of the domino problem. Memoirs of the American Mathematical Society, 1(66), 1966. URL: https://doi.org/10.1090/memo/0066.
  4. Fran Berman, David Johnson, Tom Leighton, Peter W. Shor, and Larry Snyder. Generalized planar matching. Journal of Algorithms, 11(2):153-184, 1990. URL: https://doi.org/10.1016/0196-6774(90)90001-U.
  5. Francine Berman, Frank Thomson Leighton, and Lawrence Snyder. Optimal tile salvage, 1982. Technical report, Purdue University, Department of Computer Sciences, URL: https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1321&context=cstech.
  6. Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen. Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time. SIAM Journal on Computing, 46(4):1280-1303, 2017. URL: https://doi.org/10.1137/15M1042929.
  7. Chen-Fu Chien, Shao-Chung Hsu, and Jing-Feng Deng. A cutting algorithm for optimizing the wafer exposure pattern. IEEE Transactions on Semiconductor Manufacturing, 14(2):157-162, 2001. Google Scholar
  8. J.H Conway and J.C Lagarias. Tiling with polyominoes and combinatorial group theory. Journal of Combinatorial Theory, Series A, 53(2):183-208, 1990. URL: https://doi.org/10.1016/0097-3165(90)90057-4.
  9. Dirk K. de Vries. Investigation of gross die per wafer formulas. IEEE Transactions on Semiconductor Manufacturing, 18(1):136-139, 2005. Google Scholar
  10. Dania El-Khechen, Muriel Dulieu, John Iacono, and Nikolaj Van Omme. Packing 2× 2 unit squares into grid polygons is NP-complete. In Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG 2009), pages 33-36, 2009. Google Scholar
  11. Robert J. Fowler, Michael S. Paterson, and Steven L. Tanimoto. Optimal packing and covering in the plane are NP-complete. Information processing letters, 12(3):133-137, 1981. Google Scholar
  12. George Gamow and Marvin Stern. Puzzle-math. Macmillan, 1958. Google Scholar
  13. Pawel Gawrychowski and Adam Karczmarz. Improved bounds for shortest paths in dense distance graphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pages 61:1-61:15, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.61.
  14. S. W. Golomb. Checker boards and polyominoes. The American Mathematical Monthly, 61(10):675-682, 1954. URL: https://doi.org/10.1080/00029890.1954.11988548.
  15. Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM, 32(1):130-136, 1985. Google Scholar
  16. Takashi Horiyama, Takehiro Ito, Keita Nakatsuka, Akira Suzuki, and Ryuhei Uehara. Complexity of tiling a polygon with trominoes or bars. Discret. Comput. Geom., 58(3):686-704, 2017. URL: https://doi.org/10.1007/s00454-017-9884-9.
  17. S. Jang, J. Kim, T. Kim, H. Lee, and S. Ko. A wafer map yield prediction based on machine learning for productivity enhancement. IEEE Transactions on Semiconductor Manufacturing, 32(4):400-407, 2019. Google Scholar
  18. C. Kenyon and R. Kenyon. Tiling a polygon with rectangles. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS 1992), pages 610-619, 1992. Google Scholar
  19. Hanno Melzner and Alexander Olbrich. Maximization of good chips per wafer by optimization of memory redundancy. IEEE Transactions on Semiconductor Manufacturing, 20(2):68-76, 2007. Google Scholar
  20. Gary L. Miller and Joseph Naor. Flow in planar graphs with multiple sources and sinks. SIAM Journal on Computing, 24(5):1002-1017, 1995. URL: https://doi.org/10.1137/S0097539789162997.
  21. Shay Mozes and Christian Wulff-Nilsen. Shortest paths in planar graphs with real lengths in O(nlog^2n/loglogn) time. In 16th Annual European Symposium on Algorithms (ESA 2010), 2010. URL: https://doi.org/10.1007/978-3-642-15781-3_18.
  22. Igor Pak, Adam Sheffer, and Martin Tassy. Fast domino tileability. Discrete & Computational Geometry, 56(2):377-394, 2016. URL: https://doi.org/10.1007/s00454-016-9807-1.
  23. Igor Pak and Jed Yang. Tiling simply connected regions with rectangles. Journal of Combinatorial Theory, Series A, 120(7):1804-1816, 2013. URL: https://doi.org/10.1016/j.jcta.2013.06.008.
  24. Eric Rémila. Tiling a polygon with two kinds of rectangles. Discrete Comput. Geom., 34(2):313-330, 2005. URL: https://doi.org/10.1007/s00454-005-1173-3.
  25. William P. Thurston. Conway’s tiling groups. The American Mathematical Monthly, 97(8):757-773, 1990. Google Scholar
  26. H.A.G. Wijshoff and J. van Leeuwen. Arbitrary versus periodic storage schemes and tessellations of the plane using one type of polyomino. Information and Control, 62(1):1-25, 1984. URL: https://doi.org/10.1016/S0019-9958(84)80007-8.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact