Small polyomino packing

Michael Brand

    Research output: Contribution to journalArticleResearchpeer-review

    2 Citations (Scopus)

    Abstract

    The problem of tiling a rectangle by polyominoes is known to be NP-complete if the polyominoes used are polylogarithmic in size. On the other hand, if the same is true for polyominoes of sub-logarithmic size, this would imply P=NP. This paper closes the gap between logarithmic and polylogarithmic-sized pieces by proving that tiling remains NP-complete even when only pieces of logarithmic area are used. Equivalently, we show that the problem of “small polyomino packing”, this being the packing problem where the polyominoes used are the n smallest polyominoes and the inputs are their multiplicities, is strongly NP-complete.

    Original languageEnglish
    Pages (from-to)30-34
    Number of pages5
    JournalInformation Processing Letters
    Volume126
    DOIs
    Publication statusPublished - 1 Oct 2017

    Keywords

    • Computational complexity
    • Computational geometry
    • NP-complete
    • Polyomino packing
    • Strongly NP-complete

    Cite this