Is it possible that every three dimensional convex polytope can be unfolded? If "cut" along its edges, would all faces lie flat on a plane without overlap?
While this question remains unsolved, here at Smith College under the leadership of Professor Joseph O'Rourke, a Computer Science research group has been working on the implementation of a new unfolding algorithm. The traditional interpretation of unfolding is that when the polytope is unfolded, it will be unwound to a single continuous chain of polygons connected by their edges--an edge unfolding. The algorithm we developed this summer is a new interpretation of unfolding called vertex-unfolding because the faces of the polyhedron are joined at vertices. The result of this new approach is that the surface of every simplicial (all faces are triangles) polyhedron may be cut along edges and unfolded to a planar, nonoverlapping, connected layout.
The goal of the first implementation of the algorithm was to assemble a program that would simulate the vertex-unfolding process. Using a computer to implement an algorithm is advantageous in that one can see exactly how an algorithm works--quickly and accurately, allowing one to note any errors in the process. A computer program generates the mathematical data, such as the location of vertices; the program then manipulates the data according to the rules of the algorithm. While the mathematical output generated by such a program is sufficient to verify the accuracy of an algorithm, it is laborious data to read. In order to make this process easier one must visually render the data.
Our group used a scripting language called PostScript to interpret the output. PostScript is a "page description" programming language, meaning it specifies exactly how a page should be printed. The real advantage of PostScript is that the language is device independent and always prints at a printer's highest resolution. A PostScript script is usually written on a word processing program and then submitted to a printer. In this case, I modified the unfolding program to create a file and automatically output PostScript commands to the file. Then, instead of printing the file, we used a program called Ghostscript to open the file. Ghostscript is a program that interprets PostScript and displays the picture on a computer monitor. Ghostscript was a superior alternative to printing because we could see the results immediately and did not have to waste paper on hundreds of printings.
Over the course of the program, the data was drawn twice, once displaying the polytope, as each face is removed and again as the final product of the algorithm--the chain of triangles. My work focused on rendering the removal process. As each face is "unfolded", the face is removed from the polytope leaving empty space behind. This output is essentially for error checking, allowing us to see any faces that somehow might be missed or incorrectly removed. In order to make the data easiest to interpret I wanted to show each step of the unfolding algorithm. A "step" consists of one unfolding for each face of the polytope. Since our program allows the unfolding of polytopes with any number of faces, I wanted to be able to scale and position an arbitrary number of polytopes to fit an 8 1/2in x 11in screen. I used different colors to shade the faces on the front and back of the polytope so that as each face is "peeled" away, the back is differentiated from the front (See Fig. 1). (Research supported by the NSF.)