On Unfolding 3D Lattice Polygons and 2D Orthogonal Trees
We consider the problems of unfolding 3D lattice polygons embedded on the surface of some classes of lattice polyhedra, and of unfolding 2D orthogonal trees. During the unfolding process, all graph edges are preserved and no edge crossings are allowed. Let n be the number of edges of the given polygon or tree. We show that a lattice polygon embedded on an open lattice orthotube can be convexified in O(n)moves and time, and a lattice polygon embedded on a lattice Tower of Hanoi, a lattice Manhattan Tower, or an orthogonally-convex lattice polyhedron can be convexified in O(n2) moves and time. The main technique in our algorithms is to fold up the lattice polygon from the end blocks of the given lattice polyhedron. On the other hand, we show that a 2monotone orthogonal tree on the plane can be straightened in O(n2) moves and time. We hope that our results shed some light on solving the more general conjectures, which we proposed, that a 3d lattice polygon embedded on any lattice polyhedron can always be convexified, and any 2D orthogonal tree can always be straightened.
Sheung-Hung Poon
Department of Computer Science,National Tsing Hua University,Hsinchu, Taiwan
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
374-384
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）