Unfolding well-separated orthotrees.
Because of the difficulty of the long-standing open problem of deciding whether every convex polyhedron can be edge-unfolded [DO05], attention has turned to various specializations or alterations of the original problem. To edge-unfold the surface of a polyhedron is to cut a collection of edges so that the surface may be unfolded to a planar, single-piece net. One line of investigation, started in [BDD+98], focuses on orthogonal polyhedra-those whose faces meet at angles that are multiples of 90 degrees. Although not every orthogonal polyhedron has an edge unfolding, in [BDD+98] it is shown that orthostacks have an unfolding with some cuts interior to faces (a general unfolding), and orthotubes have an edge unfolding. Subsequent work [DM04] established that a subclass of orthostacks can be edge-unfolded. The work we report here is closest to that on orthotubes, which are polyhedra made by gluing boxes face-to-face such that the dual graph (each node a box, arcs corresponding to glued faces) is a path or cycle. An orthotree is a similar polyhedron, except with the condition that the dual graph be a tree. We use the convention that each box edge is an edge of the polyhedron available for cutting (i.e., edges between coplanar faces are not \erased"). Thus, our orthotrees already include the vertex grid of edges formed by intersecting the polyhedron with coordinate planes through every box vertex. The edges of the vertex grid over more options for edge-unfolding; see [DIL04] and [DFO05]. Our main result is that a subclass of orthotrees, "well-separated" orthotrees, have an edge unfolding. The algorithm is naturally recursive on the tree structure, and we believe it shows promise for extension.
|Main Author:||Damian, Mirela.|
|Other Authors:||Flatland, Robin., Meijer, Henk., O'Rourke, Joseph.|