Paper by Erik D. Demaine
- Mirela Damian, Erik D. Demaine, and Robin Flatland, “Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm”, Graphs and Combinatorics, volume 30, number 1, 2014, pages 125–140.
We show that every orthogonal polyhedron homeomorphic to a sphere can be
unfolded without overlap while using only polynomially many (orthogonal) cuts.
By contrast, the best previous such result used exponentially many cuts.
More precisely, given an orthogonal polyhedron with n vertices,
the algorithm cuts the polyhedron only where it is met by
the grid of coordinate planes passing through the vertices,
together with Θ(n2) additional coordinate planes
between every two such grid planes.
- The paper is 18 pages.
- The paper is available in PDF (2001k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated March 26, 2017 by