McGill University - School of Computer Science

Algorithms Seminar

(formerly: Computational Geometry Seminar)

Everybody is welcome.

DATE:	Wednesday, October 28th, 1998
TIME:	16:00-17:00
PLACE:	McConnell 320
TITLE:	Folding and Cutting Paper
SPEAKER:	Erik Demaine, University of Waterloo

Take a sheet of paper, fold it flat, and make one complete straight cut. What shapes can the unfolded pieces make? The earliest reference to this idea is a story about Betsy Ross showing George Washington how easily a regular five-pointed star could be made for the American flag, by folding a sheet of paper flat and making one straight cut with scissors. Houdini used folding and cutting for a magic trick before he became a famous escape artist. This talk discusses our work on the fold-and-cut problem: given a collection of line segments (i.e., a plane graph), find a flat folding of the plane so that precisely those line segments are folded to a common line, along which we can cut to make the desired shapes.

I will describe two algorithms that we have developed to solve this problem for any collection of line segments: convex and nonconvex polygons, multiple disjoint polygons, adjoining polygons, nested polygons, and even floating line segments and points. The first algorithm (joint work with Martin Demaine and Anna Lubiw) is based on the straight skeleton. The second algorithm (joint work with Marshall Bern, David Eppstein, and Barry Hayes) is based on disk packing.

This information is available at http://cgm.cs.mcgill.ca/~therese/seminar.
Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to Therese Biedl at therese@cgm.cs.mcgill.ca.