Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
The existence of convex polyhedra without non-overlapping unfoldings 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. –  Steven Stadnicki Nov 14 '12 at 20:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.