Paper by Erik D. Demaine
- Yasuhiko Asao, Erik D. Demaine, Martin L. Demaine, Hideaki Hosaka, Akitoshi Kawamura, Tomohiro Tachi, and Kazune Takahashi, “Folding and Punching Paper”, Journal of Information Processing, to appear. Special issue of papers from the 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games
We show how to fold a piece of paper and punch one hole so as to produce any
desired pattern of holes. Given n points on a piece of paper (finite
polygon or infinite plane), we give algorithms to fold the paper flat so that
those n points and no other points of paper map to a common location,
so that punching one hole and unfolding produces exactly the desired pattern
of holes. Furthermore, we can forbid creases from passing through the points
(allowing noncircular hole punches). Our solutions use relatively few creases
(in some cases, polynomially many), and can be expressed as a linear sequence
of folding steps of complexity O(1)—a generalization of simple
folds which we introduce.
- The paper is 11 pages.
- The paper is available in PDF (6411k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- FoldPunch_JCDCGGG2016 (Folding and Punching Paper)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated July 25, 2017 by