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 NPcomplete 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 NPcompleteness proofs rely heavily on the regions having lots of holes. We construct a fixed set of rectangular tiles whose tileability problem is NPcomplete even for simply connected regions.
Joint work with Igor Pak.
Files:
Speaker: Jed Yang
Institution: UCLA
Event Organizer:
