Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm
We show that every orthogonal polyhedron homeomorphic to a sphere can be unfolded without overlap while using only polynomially many (orthogonal) cuts. By contrast, the best previous such result used exponentially many cuts. More precisely, given an orthogonal polyhedron with n vertices, the algorit...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2014
|
| Online Access: | http://hdl.handle.net/1721.1/86067 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1811080714836246528 |
|---|---|
| author | Damian, Mirela Demaine, Erik D. Flatland, Robin |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Damian, Mirela Demaine, Erik D. Flatland, Robin |
| author_sort | Damian, Mirela |
| collection | MIT |
| description | We show that every orthogonal polyhedron homeomorphic to a sphere can be unfolded without overlap while using only polynomially many (orthogonal) cuts. By contrast, the best previous such result used exponentially many cuts. More precisely, given an orthogonal polyhedron with n vertices, the algorithm cuts the polyhedron only where it is met by the grid of coordinate planes passing through the vertices, together with Θ(n [superscript 2]) additional coordinate planes between every two such grid planes. |
| first_indexed | 2024-09-23T11:35:37Z |
| format | Article |
| id | mit-1721.1/86067 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:35:37Z |
| publishDate | 2014 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/860672022-10-01T04:39:08Z Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm Damian, Mirela Demaine, Erik D. Flatland, Robin Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. We show that every orthogonal polyhedron homeomorphic to a sphere can be unfolded without overlap while using only polynomially many (orthogonal) cuts. By contrast, the best previous such result used exponentially many cuts. More precisely, given an orthogonal polyhedron with n vertices, the algorithm cuts the polyhedron only where it is met by the grid of coordinate planes passing through the vertices, together with Θ(n [superscript 2]) additional coordinate planes between every two such grid planes. National Science Foundation (U.S.) (CAREER Award CCF-0347776) 2014-04-07T17:58:47Z 2014-04-07T17:58:47Z 2012-11 2012-10 Article http://purl.org/eprint/type/JournalArticle 0911-0119 1435-5914 http://hdl.handle.net/1721.1/86067 Damian, Mirela, Erik D. Demaine, and Robin Flatland. “Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm.” Graphs and Combinatorics 30, no. 1 (January 2014): 125–140. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1007/s00373-012-1257-9 Graphs and Combinatorics Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag MIT web domain |
| spellingShingle | Damian, Mirela Demaine, Erik D. Flatland, Robin Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm |
| title | Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm |
| title_full | Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm |
| title_fullStr | Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm |
| title_full_unstemmed | Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm |
| title_short | Unfolding Orthogonal Polyhedra with Quadratic Refinement: The Delta-Unfolding Algorithm |
| title_sort | unfolding orthogonal polyhedra with quadratic refinement the delta unfolding algorithm |
| url | http://hdl.handle.net/1721.1/86067 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT damianmirela unfoldingorthogonalpolyhedrawithquadraticrefinementthedeltaunfoldingalgorithm AT demaineerikd unfoldingorthogonalpolyhedrawithquadraticrefinementthedeltaunfoldingalgorithm AT flatlandrobin unfoldingorthogonalpolyhedrawithquadraticrefinementthedeltaunfoldingalgorithm |