{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T03:47:25Z","timestamp":1648871245815},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2009,6]]},"abstract":"<jats:p> 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(n<jats:sup>2<\/jats:sup>) 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(n) moves and in O(n log n) time. Finally, we show that two special classes of diameter-4 trees in two dimensions can always be straightened. <\/jats:p>","DOI":"10.1142\/s0218195909002964","type":"journal-article","created":{"date-parts":[[2009,6,25]],"date-time":"2009-06-25T02:31:29Z","timestamp":1245897089000},"page":"289-321","source":"Crossref","is-referenced-by-count":0,"title":["ON UNFOLDING LATTICE POLYGONS\/TREES AND DIAMETER-4 TREES"],"prefix":"10.1142","volume":"19","author":[{"given":"SHEUNG-HUNG","family":"POON","sequence":"first","affiliation":[{"name":"Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 300, R.O.C."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00150-8"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00229-3"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-001-0038-7"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.12.004"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1142\/S0218216598000553"},{"key":"rf8","first-page":"24","author":"Chan H. S.","journal-title":"Phys. Today"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00013-X"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/304\/05200"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-0006-7"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1021\/bi00483a001"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1511\/1998.25.3306"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195909002964","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:16:21Z","timestamp":1565190981000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195909002964"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":11,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2009,6]]}},"alternative-id":["10.1142\/S0218195909002964"],"URL":"https:\/\/doi.org\/10.1142\/s0218195909002964","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6]]}}}