Edge-unfolding almost-flat convex polyhedral terrains

[摘要] In this thesis we consider the centuries-old question of edge-unfolding convex polyhedra, focusing specifically on edge-unfoldability of convex polyhedral terrain which are ;;almost at;; in that they have very small height. We demonstrate how to determine whether cut-trees of such almost-at terrains unfold and prove that, in this context, any partial cut-tree which unfolds without overlap and ;;opens;; at a root edge can be locally extended by a neighboring edge of this root edge. We show that, for certain (but not all) planar graphs G, there are cut-trees which unfold for all almost-at terrains whose planar projection is G. We also demonstrate a non-cut-tree-based method of unfolding which relies on ;;slice;; operations to build an unfolding of a complicated terrain from a known unfolding of a simpler terrain. Finally, we describe several heuristics for generating cut-forests and provide some computational results of such heuristics on unfolding almost-at convex polyhedral terrains.

[发布机构] Massachusetts Institute of Technology