Grid Vertex-Unfolding Orthogonal Polyhedra
| 详细信息 | 推荐本文 | |
- 作者：Mirela Damian ; Robin Flatland and Joseph O鈥橰ourke
- 关键词：Vertex ; unfolding ; Grid unfolding ; Orthogonal polyhedra ; Genus ; zero
- 刊名：Discrete and Computational Geometry
- 出版时间：March, 2008
- 出版年：2008
- 期刊代码：48_0179-5376
- 类别：mat
- 卷：39
- 期：1-3
- 页码：213-238
- 数据来源：sp
摘要
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(n 2) time. Enroute to explaining this algorithm, we present a simpler vertex-unfolding algorithm that requires a 3脳1脳1 refinement of the vertex grid.