3
$\begingroup$

I'm interested in learning more on unfolding polyhedra.

  1. Are there any known algorithms that unfold polyhedra into nets? I'm interested in writing code on this in either MATLAB, Python, or C#.
  2. On this page, Joseph O'Rourke goes into several unfoldings of a cube. What resources are there for studying the differences (or equivalencies) between the unfoldings?

1 Answers 1

2

Counting the unfoldings

If you consider your polyhedron as a graph, with one vertex per face, and two vertices connected if the corresponding faces are adjacent, if your polyhedron has no vertex such that the sum of surrounding angles is $2\pi$ then I would say the number of unfoldings corresponds to the number of covering trees of this graph quotiented by the symmetries of your polyhedron. This question on counting the number of covering trees of a graph provides some insight on this problem and therefore on the potential number of unfoldings you may get.

Computing one unfolding

If what you want is solely to compute one unfolding, then my strategy would be to use a breadth first traversal of the graph corresponding to your polyhedron to determine which adjacent faces should be kept glued in the unfolding. This technique is commonly used in algorithms for mesh parametrization in graphics, for texture mapping for instance. Roughly :

  • take a random face $f_0$ and flatten in on the plane ;
  • mark this face as done ;
  • for each neighbouring face $f_i$ adjacent to $f_0$ :
    • add $(f_0,f_i)$ to a queue ;
    • mark $f_i$ as done ;
  • while the queue is not empty :
    • extract $(f_0,f_i)$ from the queue ;
    • unfold $f_i$ rigidly next to $f_0$ ;
    • for each neighbouring face $f_j$ of $f_i$ which is not marked as done :
      • add $(f_i,f_j)$ to the queue ;
      • mark $f_j$ as done.

Note however that this algorithm does not care on whether several unfolded faces overlap. I believe an example of a polyhedron which cannot be unfolded in a single piece without overlaps may be found, however I can't exhibit any which is compact. I believe this is related to surfaces with negative Gaussian curvature everywhere.

  • 1
    The existence o$f$ convex polyhedra without non-overlapping un$f$oldings is an open problem. For non-convex (even star-shaped) polyhedra it's relatively straightforward to exhibit: imagine, for instance, a cube with a 'spike' added to the center of each face.2012-11-14