TY - GEN
T1 - On unfolding 3D lattice polygons and 2D orthogonal trees
AU - Poon, Sheung Hung
N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
PY - 2008
Y1 - 2008
N2 - 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 2-monotone 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.
AB - 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 2-monotone 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.
UR - http://www.scopus.com/inward/record.url?scp=48249150674&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-69733-6_37
DO - 10.1007/978-3-540-69733-6_37
M3 - Conference contribution
AN - SCOPUS:48249150674
SN - 3540697322
SN - 9783540697329
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 374
EP - 384
BT - Computing and Combinatorics - 14th Annual International Conference, COCOON 2008, Proceedings
T2 - 14th Annual International Conference on Computing and Combinatorics, COCOON 2008
Y2 - 27 June 2008 through 29 June 2008
ER -