Paper by Martin L. Demaine

Reference:

Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, and Godfried T. Toussaint, “Hiding Disks in Folded Polygons”, in Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG'98), Montréal, Québec, Canada, August 10–12, 1998.

Abstract:

This paper considers the problem of finding a simple fold of a given polygon P that “hides” (covers both sides of) the largest possible disk. We solve this problem by giving a polynomial-time algorithm to find the largest pair of equal-radius non-overlapping disks in a polygon P. The desired fold is then the perpendicular bisector of the centers of these two disks. We also present some conjectures for the more general multiple-fold case when P is a square.

Comments:

This paper is also available from the electronic proceedings as http://cgm.cs.mcgill.ca/cccg98/proceedings/cccg98-biedl-hiding.ps.gz.

Updates:

One problem explored in this paper, packing the largest pair of equal-radius disks in a given polygon, have been further developed in several followup papers. See my webpage on wrapping for a summary and references.

Erin McLeish prepared an excellent webpage describing these and related results and algorithms, including a Java applet.

Length:

The paper is 11 pages and the talk is 20 minutes.

Availability:

The paper is available in PostScript (194k).

See information on file formats.

[Google Scholar search]

Related webpages:

Wrapping Polyhedra (Erik Demaine)