×

Ununfoldable polyhedra with convex faces. (English) Zbl 1021.52013

A classic open question in geometry is whether every convex polyhedron can be cut along its edges and flattened into the plane without any overlap. Such a collection of cuts is called an edge cutting of the polyhedron, and the resulting simple polygon is called an edge unfolding or net.
The authors investigate the limits of unfoldability by studying nonconvex polyhedra with the same combinatorial structure as convex polyhedra. Two examples of polyhedra are given, one with 24 convex faces and one with 36 triangular faces that cannot be unfolded by cutting along edges. This proves, in particular, that the edge-unfolding conjecture does not generalize to topologically convex polyhedra. It is shown that cuts across faces can unfold some convex-faced polyhedra that cannot be unfolded with cuts only along edges. This is the first demonstration that general cuts are more powerful than edge cuts.
The problem of constructing a polyhedron that cannot be unfolded even using general cuts is also considered. Finding a “closed” ununfoldable polyhedron is an intriguing open problem. As a step towards this goal, the authors present an “open” polyhedron with triangular faces that cannot be unfoldable no matter how it is cut.

MSC:

52C45 Combinatorial complexity of geometric structures
52B10 Three-dimensional polytopes

Software:

UnfoldPolytope
Full Text: DOI

References:

[1] Agarwal, P. K.; Aronov, B.; O’Rourke, J.; Schevon, C. A., Star unfolding of a polytope with applications, SIAM J. Comput., 26, 6, 1689-1713 (1997) · Zbl 0891.68117
[2] Aronov, B.; O’Rourke, J., Nonoverlap of the star unfolding, Discrete Comput. Geom., 8, 3, 219-250 (1992) · Zbl 0756.52011
[3] Bern, M.; Demaine, E. D.; Eppstein, D.; Kuo, E., Ununfoldable polyhedra, (Proceedings of the 11th Canadian Conference on Computational Geometry, Vancouver, Canada (1999)), http://www.cs.ubc.ca/conferences/CCCG/elec_proc/fp38.ps.gz. Also Technical Report CS-99-04, Department of Computer Science, University of Waterloo, August 1999
[4] Biedl, T.; Demaine, E.; Demaine, M.; Lubiw, A.; Overmars, M.; O’Rourke, J.; Robbins, S.; Whitesides, S., Unfolding some classes of orthogonal polyhedra, (Proceedings of the 10th Canadian Conference on Computational Geometry, Montréal, Canada (1998)), http://cgm.cs.mcgill.ca/cccg98/proceedings/cccg98-biedl-unfolding.ps.gz
[5] Croft, H. T.; Falconer, K. J.; Guy, R. K., (Unsolved Problems in Geometry (1991), Springer-Verlag), 73-76 · Zbl 0748.52001
[6] Cromwell, P. R., Polyhedra (1997), Cambridge University Press · Zbl 0888.52012
[7] Cundy, H. M.; Rollett, A. P., Polyhedra, (Mathematical Models (1961), Oxford University Press), Chapter 3, pp. 76-160 · Zbl 0095.38001
[8] E. Demaine, M. Demaine, A. Lubiw, J. O’Rourke, Examples, counterexamples, and enumeration results for foldings and unfoldings between polygons and polytopes, Technical Report 069, Smith College, Northampton, MA, July 2000. http://www.arXiv.org/abs/cs.CG/0007019; E. Demaine, M. Demaine, A. Lubiw, J. O’Rourke, Examples, counterexamples, and enumeration results for foldings and unfoldings between polygons and polytopes, Technical Report 069, Smith College, Northampton, MA, July 2000. http://www.arXiv.org/abs/cs.CG/0007019
[9] Demaine, E. D.; Demaine, M. L.; Lubiw, A.; O’Rourke, J., Enumerating foldings and unfoldings between polygons and polytopes, (Proceedings of the Japan Conference on Discrete and Computational Geometry, Tokyo, Japan (2000)), http://www.arXiv.org/abs/cs.CG/0107024 · Zbl 0996.52009
[10] E.D. Demaine, D. Eppstein, J. Erickson, G.W. Hart, J. O’Rourke, Vertex-unfoldings of simplicial polyhedra, July 2001, arXiv:cs.CG/0107023. http://www.arXiv.org/abs/cs.CG/0107023; E.D. Demaine, D. Eppstein, J. Erickson, G.W. Hart, J. O’Rourke, Vertex-unfoldings of simplicial polyhedra, July 2001, arXiv:cs.CG/0107023. http://www.arXiv.org/abs/cs.CG/0107023
[11] Dürer, A., The Painter’s Manual: A Manual of Measurement of Lines, Areas, and Solids by Means of Compass and Ruler Assembled by Albrecht Dürer for the Use of All Lovers of Art with Appropriate Illustrations Arranged to be Printed in the Year MDXXV (1977), Abaris Books: Abaris Books New York, English translation of: Unterweysung der Messung mit dem Zirkel un Richtscheyt in Linien Ebnen uhnd Gantzen Corporen, 1525
[12] K. Fukuda, Strange unfoldings of convex polytopes, June 1997. http://www.ifor.math.ethz.ch/staff/fukuda/unfold_home/unfold_open.html; K. Fukuda, Strange unfoldings of convex polytopes, June 1997. http://www.ifor.math.ethz.ch/staff/fukuda/unfold_home/unfold_open.html
[13] Grünbaum, B., Convex Polytopes (1967), Interscience: Interscience New York · Zbl 0163.16603
[14] Gupta, S. K.; Bourne, D. A.; Kim, K. H.; Krishnan, S. S., Automated process planning for sheet metal bending operations, J. Manufacturing Systems, 17, 5, 338-360 (1998)
[15] B. Hayes, Pleasures of plication, American Scientist, November-December 1995. See also http://www.cs.colorado.edu/ eisenbea/hypergami/; B. Hayes, Pleasures of plication, American Scientist, November-December 1995. See also http://www.cs.colorado.edu/ eisenbea/hypergami/
[16] Henk, M.; Richter-Gebert, J.; Ziegler, G. M., Basic properties of convex polytopes, (Goodman, J. E.; O’Rourke, J., Handbook of Discrete and Computational Geometry (1997), CRC Press: CRC Press Boca Raton), Chapter 13, pp. 243-270 · Zbl 0911.52007
[17] Lundstrom Design, Touch-3d, July 1998. http://www.algonet.se/ ludesign/; Lundstrom Design, Touch-3d, July 1998. http://www.algonet.se/ ludesign/
[18] Mitchell, J. S.B.; Mount, D. M.; Papadimitriou, C. H., The discrete geodesic problem, SIAM J. Comput., 16, 4, 647-668 (1987) · Zbl 0625.68051
[19] M. Namiki, K. Fukuda, Unfolding 3-dimensional convex polytopes: A package for Mathematica 1.2 or 2.0, Version 1.0, September 1994. ftp://ftp.ifor.math.ethz.ch/pub/fukuda/mathematica/UnfoldPolytope.tar.Z; M. Namiki, K. Fukuda, Unfolding 3-dimensional convex polytopes: A package for Mathematica 1.2 or 2.0, Version 1.0, September 1994. ftp://ftp.ifor.math.ethz.ch/pub/fukuda/mathematica/UnfoldPolytope.tar.Z
[20] O’Rourke, J., Folding and unfolding in computational geometry, (Revised Papers from the Japan Conference on Discrete and Computational Geometry, Tokyo, Japan. Revised Papers from the Japan Conference on Discrete and Computational Geometry, Tokyo, Japan, Lecture Notes in Computer Science, 1763 (1998)), 258-266 · Zbl 0971.68602
[21] C. Schevon, Unfolding polyhedra. sci.math Usenet article, February 1987. See http://www.ics.uci.edu/ eppstein/gina/unfold.html; C. Schevon, Unfolding polyhedra. sci.math Usenet article, February 1987. See http://www.ics.uci.edu/ eppstein/gina/unfold.html
[22] C. Schevon, Algorithms for geodesics on polytopes, PhD Thesis, Johns Hopkins University, 1989; C. Schevon, Algorithms for geodesics on polytopes, PhD Thesis, Johns Hopkins University, 1989 · Zbl 0678.52004
[23] Sharir, M.; Schorr, A., On shortest paths in polyhedral spaces, SIAM J. Comput., 15, 1, 193-215 (1986) · Zbl 0612.68090
[24] Shephard, G. C., Convex polytopes with convex nets, Math. Proc. Cambridge Philos. Soc., 78, 389-403 (1975) · Zbl 0312.52011
[25] Steinitz, E.; Rademacher, H., Vorlesungen über die Theorie der Polyeder (1934), Springer-Verlag: Springer-Verlag Berlin, Reprinted 1976 · Zbl 0325.52001
[26] C.-H. Wang, Manufacturability-driven decomposition of sheet metal, PhD Thesis, Carnegie Mellon University, Robotics Institute, Technical Report CMU-RI-TR-97-35, September 1997; C.-H. Wang, Manufacturability-driven decomposition of sheet metal, PhD Thesis, Carnegie Mellon University, Robotics Institute, Technical Report CMU-RI-TR-97-35, September 1997
[27] Wenninger, M. J., Polyhedron Models (1971), Cambridge University Press · Zbl 0222.50010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.