Rutgers Discrete Mathematics Seminar

Title: Tiling simply connected regions using rectangles

Speaker: Jed Yang, UCLA

Date: Tuesday, November 13, 2012 2:00pm

Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ


Given a set of tiles on a square grid (think polyominoes) and a region, can we tile the region by copies of the tiles? In general this decision problem is undecidable for infinite regions and NP-complete for finite regions. In the case of simply connected finite regions, the problem can be solved in polynomial time for a pair of rectangular tiles using combinatorial group theory; whereas the NP-completeness proofs rely heavily on the regions having lots of holes. We construct a fixed set of rectangular tiles whose tileability problem is NP-complete for simply connected regions. Joint work with Igor Pak.