A disk-packing algorithm for an origami magic trick

Marshall Wayne Bern,
Erik D. Demaine,
David Eppstein,
and Barry Hayes

*Origami$^3$: Proc. 3rd Int. Mtg. Origami Science, Math, and Education (3OSME), Asilomar, Calif., 2001*, Thomas Hull, ed., A K Peters, 2002, pp. 17–28

*Mathematical Reviews* 2004b:52030, 2004

Reviewed by Uwe Schnell

The problem of folding a sheet of paper so that a single straight cut produces a cut-out of a certain figure can be formulated mathematically as follows: Given a polygon with holes $P$ and a rectangle $R \supset P$, find a flat-folding of $R$ such that the cross-section of the folding with a perpendicular plane is the boundary of $P$. The authors give an algorithm to solve this problem. The strategy is to pack disks such that the disk centers induce a mixed triangulation/quadrangulation respecting the boundary of the polygon. The algorithm is based on results by R. J. Lang [in Proceedings of the twelfth annual symposium on computational geometry (Philadelphia, PA, 1996), 98--105, ACM, NY, 1996] and M. W. Bern and D. Eppstein \ref[Internat. J. Comput. Geom. Appl. 2 (1992), no. 3, 241--255; MR1194449 (94e:52016a)].