Date: Friday, October 05, 2012
Location: 3866 East Hall (4:10 PM to 5:00 PM)
Title: Tiling simply connected regions with rectangles
Abstract: 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 some special sets of tiles using 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 even for simply connected regions.
Joint work with Igor Pak.
Speaker: Jed Yang
Institution: UCLA
Event Organizer:
| 
