Paper by Erik D. Demaine

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.

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.

This paper is also available from the electronic proceedings as

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.

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

The paper is available in PostScript (194k).
The talk is also available in PostScript (148k).
See information on file formats.
[Google Scholar search]

Related webpages:
Wrapping Polyhedra

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated May 28, 2024 by Erik Demaine.