@inproceedings{edb5054a27f74accad258f3044f9c133,

title = "On unfolding lattice polygons/trees and diameter-4 trees",

abstract = "We consider the problems of straightening polygonal trees and convexifying polygons by continuous motions such that rigid edges can rotate around vertex joints and no edge crossings are allowed. A tree can be straightened if all its edges can be aligned along a common straight line such that each edge points {"}away{"} from a designated leaf node. A polygon can be convexified if it can be reconfigured to a convex polygon. A lattice tree (resp. polygon) is a tree (resp. polygon) containing only edges from a square or cubic lattice. We first show that a 2D lattice chain or a 3D lattice tree can be straightened efficiently in O(n) moves and time, where n is the number of tree edges. We then show that a 2D lattice tree can be straightened efficiently in O(n2) moves and time. Furthermore, we prove that a 2D lattice polygon or a 3D lattice polygon with simple shadow can be convexified efficiently in O(n2) moves and time. Finally, we show that two special classes of diameter-4 trees in two dimensions can always be straightened.",

keywords = "Comput. geom, Convexifying, Straightening, Unfolding",

author = "Poon, {Sheung Hung}",

year = "2006",

doi = "10.1007/11809678_21",

language = "English",

isbn = "3540369252",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "186--195",

booktitle = "Computing and Combinatorics - 12th Annual International Conference, COCOON 2006, Proceedings",

address = "Germany",

note = "12th Annual International Conference on Computing and Combinatorics, COCOON 2006 ; Conference date: 15-08-2006 Through 18-08-2006",

}