Paper by Erik D. 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.

BibTeX

@InProceedings{CCCG98a,
  AUTHOR        = {Therese C. Biedl and Erik D. Demaine and Martin L. Demaine
                   and Anna Lubiw and Godfried T. Toussaint},
  TITLE         = {Hiding Disks in Folded Polygons},
  BOOKTITLE     = {Proceedings of the 10th Canadian Conference on Computational
                   Geometry (CCCG'98)},
  bookurl       = {http://cgm.cs.mcgill.ca/cccg98/},
  ADDRESS       = {Montr\'eal, Qu\'ebec, Canada},
  MONTH         = {August 10--12},
  YEAR          = 1998,
  WEBPAGES      = {wrapping},
  length        = {11 pages; 20 minutes},
  dblp          = {https://dblp.org/rec/conf/cccg/BiedlDDLT98},
  ee            = {http://cgm.cs.mcgill.ca/cccg98/proceedings/cccg98-biedl-hiding.ps.gz},
  comments      = {This paper is also available from the <A
                   HREF="http://cgm.cs.mcgill.ca/cccg98/proceedings/">
                   electronic proceedings</A> as <A
                   HREF="http://cgm.cs.mcgill.ca/cccg98/proceedings/cccg98-biedl-hiding.ps.gz">http://cgm.cs.mcgill.ca/cccg98/proceedings/cccg98-biedl-hiding.ps.gz</A>.},
  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
                   <A HREF="../../wrapping/">wrapping</A> for a summary
                   and references.
                   <P>
                   Erin McLeish prepared an excellent
                   <A HREF="http://jeff.cs.mcgill.ca/~mcleish/507/disk_hiding.html">webpage
                   describing these and related results and algorithms</A>,
                   including a Java applet.},
  unrefereed    = 1,
}

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).

The talk is also available in PostScript (148k).

See information on file formats.

[Google Scholar search]

Related webpages:

Wrapping Polyhedra