Grid Vertex-Unfolding Orthogonal Polyhedra
| dc.creator | Damian, Mirela | |
| dc.creator | Flatland, Robin | |
| dc.creator | O'Rourke, Joseph | |
| dc.date | 2005-09-19 | |
| dc.date | 2006-09-27 | |
| dc.date.accessioned | 2026-07-07T06:41:57Z | |
| dc.date.available | 2026-07-07T06:41:57Z | |
| dc.description | 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 permits faces in the net to be connected at single vertices, not necessarily along edges. We show that any orthogonal polyhedron 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 x 1 refinement of the vertex grid. | |
| dc.description | Original: 12 pages, 8 figures, 11 references. Revised: 22 pages, 16 figures, 12 references. New version is a substantial revision superceding the preliminary extended abstract that appeared in Lecture Notes in Computer Science, Volume 3884, Springer, Berlin/Heidelberg, Feb. 2006, pp. 264-276 | |
| dc.identifier | https://arxiv.org/abs/cs/0509054 | |
| dc.identifier | http://arxiv.org/abs/cs/0509054 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/101860 | |
| dc.subject | Computational Geometry | |
| dc.subject | Discrete Mathematics | |
| dc.subject | F.2.2 | |
| dc.title | Grid Vertex-Unfolding Orthogonal Polyhedra | |
| dc.type | text |