Marc Van Kreveld

Thursday, April 26 at 9:00 AM

Abstract

There are many puzzles in the world, both physical and digital ones. From the algorithms research perspective, a lot of attention has been given to combinatorial and graph-based puzzles and how to solve them. We will focus on puzzles with a geometric component and where techniques from discrete and computational geometry can be employed to generate them. Automated generation of puzzles is arguably more useful than automated solving. We will see new connect-the-dots puzzles, new nonogram puzzles, new graph planarization puzzles, and the app game called Lines!

Download the slides for this lecture