Seminar Event Detail


Combinatorics

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.

Files:


Speaker:  Jed Yang
Institution:  UCLA

Event Organizer:     

 

Edit this event (login required).
Add new event (login required).
For access requests and instructions, contact math-webmaster@umich.edu

Back to previous page
Back to UM Math seminars/events page.