Geometric Puzzles: Algorithms and Complexity
Speaker:
Erik Demaine, Massachusetts Institute of Technology
Date and Time:
Friday, October 14, 2011 - 11:00am to 12:00pm
Location:
Fields Institute, Room 230
Abstract:
I love geometry because the problems and solutions are fun and often tangible. Puzzles are one way to express these two features, and are also a great source of their own computational geometry problems: which puzzles can be solved and/or designed efficiently using computer algorithms? Proving puzzles to be computationally difficult leads to a mathematical sort of puzzle, designing gadgets to build computers out of puzzles. I will describe a variety of algorithmic and computational complexity results on geometric puzzles, focusing on more playful and recent results.