Grid Vertex-Unfolding Orthogonal Polyhedra

Abstract An edge-unfolding of a polyhedron is produced by cutting along edges and flattening the faces to a net, a connected planar piece with no overlaps. A grid unfolding allows additional cuts along grid edges induced by coordinate planes passing through every vertex. A vertex-unfolding allows faces in the net to be connected at single vertices, not necessarily along edges. We show that any orthogonal polyhedra of genus zero has a grid vertex-unfolding. (There are orthogonal polyhedra that cannot be vertex-unfolded, so some type of “gridding” of the faces is necessary.) For any orthogonal polyhedron P with n vertices, we describe an algorithm that vertex-unfolds P in O(n2) time. Enroute to explaining this algorithm, we present a simpler vertex-unfolding algorithm that requires a 3×1×1 refinement of the vertex grid.

• Publication year

  2005

• Venue

  Symposium on Theoretical Aspects of Computer Science

• Publication date

  2005-09-18

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/11672142_21arXiv cs/0509054
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Geometric Folding Algorithms: Linkages, Origami, Polyhedra

  2007cited by this paper
• A Survey of Folding and Unfolding in Computational Geometry

  2007cited by this paper
• Geometric Folding Algorithms: Linkages

  2007cited by this paper
• PolyCube-Maps

  2004cited by this paper
• Grid Vertex-Unfolding Orthostacks

  2004cited by this paper
• November 2004

  2004cited by this paper
• Folding and unfolding

  2002cited by this paper
• Open problems from cccg 2001

  2002cited by this paper
• Vertex-unfoldings of simplicial manifolds

  2001influential reference
• Folding and Unfolding in Computational Geometry

  1998cited by this paper
• Automated process planning for sheet metal bending operations

  1998cited by this paper
• Unfolding some classes of orthogonal polyhedra

  1998cited by this paper
• Manufacturability-Driven Decomposition of Sheet Metal Products

  1997cited by this paper
• Optimal binary space partitions for orthogonal objects

  1990cited by this paper
• A Numerical Solution to the Generalized Mapmaker's Problem: Flattening Nonconvex Polyhedral Surfaces

  1989cited by this paper

• String Mechanism for Polyhedral Pop-up Card Design

  2021cites this paper
• Mill and fold: Shape simplification for fabrication

  2019cites this paper
• Rectangular Unfoldings of Polycubes

  2019cites this paper
• Vertex Unfoldings of Orthogonal Polyhedra: Positive, Negative, and Inconclusive Results

  2018influential citation
• Polycube Unfoldings Satisfying Conway ’ s Criterion

  2016cites this paper
• Unfolding Rectangle-Faced Orthostacks

  2012cites this paper
• Common Unfoldings of Polyominoes and Polycubes

  2010cites this paper
• Geometric Folding Algorithms: Linkages

  2007cites this paper
• Epsilon-Unfolding Orthogonal Polyhedra

  2006influential citation
• Grid Vertex-Unfolding Orthostacks

  2004cites this paper