Tiling a Polygon with Rectangles

The authors study the problem of tiling a simple polygon of surface n with rectangles of given types (tiles). They present a linear time algorithm for deciding if a polygon can be tiled with 1 * m and k * 1 tiles (and giving a tiling when it exists), and a quadratic algorithm for the same problem when the tile types are m * k and k * m. >

Authors

• Claire Mathieu
• Richard W. Kenyon

Keywords

• Tiles
• Running Time
• Reachable
• Exhaustive Search
• Highest Point
• Linear Time
• Pair Of Points
• Blockchain
• Interior Point
• Line Graph
• Flow Problem
• Sequence Blocks
• Proof Of The Lemma
• Function Of Height
• Dimer Model
• High-level Description
• Idea Of The Proof
• Horizontal Edges
• Linear-time Algorithm