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.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math