Special Issue: Selected Papers from the 12th Annual International Computing and Combinatorics Conference (COCOON'2006), 15–18 August 2006, Institute of Information Science, Academia Sinica, Taipei, TaiwanNo Access

ON UNFOLDING LATTICE POLYGONS/TREES AND DIAMETER-4 TREES

SHEUNG-HUNG POON

SHEUNG-HUNG POON

Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 300, R.O.C.

Search for more papers by this author

https://doi.org/10.1142/S0218195909002964Cited by:0 (Source: Crossref)

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(n²) 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.

A preliminary version of this paper appears at 12th Annual International Computing and Combinatorics Conference¹⁶.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in image analysis!

References

J. Alberto-Calvoet al., Inform. Process. Lett. 80(2), 81 (2001). Crossref, Web of Science, Google Scholar
H. Altet al., The complexity of (un)folding, Proc. 19th ACM Symp. Computational Geometry (SoCG) (2003) pp. 164–170. Google Scholar
T. Biedlet al., Discr. Appl. Math. 117(1-3), 293 (2002), DOI: 10.1016/S0166-218X(01)00229-3. Crossref, Web of Science, Google Scholar
T. Biedlet al., Discr. Comput. Geom. 26(3), 269 (2001). Crossref, Web of Science, Google Scholar
T. Biedl, A. Lubiw and J. Sun, Comput. Geom.: Th. Appl. 31(3), 207 (2005), DOI: 10.1016/j.comgeo.2004.12.004. Crossref, Web of Science, Google Scholar
J. Cantarellaet al., An energy-driven approach to linkage unfolding, Proc. 20th Ann. ACM Symp. Computational Geometry (SoCG) (2004) pp. 134–143. Google Scholar
J. Cantarella and H. Johnston, J. Knot Theory Ramifications 7, 1027 (1998), DOI: 10.1142/S0218216598000553. Link, Web of Science, Google Scholar
H. S. Chan and K. A. Dill, Phys. Today 24 (1993), DOI: 10.1063/1.881371. Google Scholar
R. Cocan and J. O'Rourke, Comput. Geom.: Th. Appl. 20, 105 (2001), DOI: 10.1016/S0925-7721(01)00013-X. Crossref, Web of Science, Google Scholar
R. Connelly, E. Demaine and G. Rote, Physical Knots: Knotting, Linking, and Folding of Geometric Objects in R3, eds. J. Calvo, K. Millett and E. Rawdon (American Mathematical Society, 2002) pp. 287–311. Crossref, Google Scholar
R. Connelly, E. D. Demaine and G. Rote, Discr. Comput. Geom. 30(2), 205 (2003). Crossref, Web of Science, Google Scholar
E. D. Demaineet al., Interlocked open linkages with few joints, Proc. 18th Ann. ACM Symp. Computational Geometry (SoCG) (2002) pp. 189–198. Google Scholar
K. A. Dill, Biochemistry 29(31), 7133 (1990), DOI: 10.1021/bi00483a001. Crossref, Web of Science, Google Scholar
B. Hayes, American Scientist 86, 216 (1998). Crossref, Web of Science, Google Scholar
S.-H. Poon, On straightening low-diameter unit trees, Proc. 13th Int. Symp. Graph Drawing (GD) (2005) pp. 519–521. Google Scholar
S.-H. Poon, On unfolding lattice polygons/trees and diameter-4 trees, Proc. 12th Ann. Int. Comput. Combinatorics Conference (COCOON) (2006) pp. 186–195. Google Scholar
I. Streinu, A combinatorial approach for planar non-colliding robot arm motion planning, Proc. 41st ACM Ann. Symp. Foundations of Computer Science (FOCS) (2000) pp. 443–453. Google Scholar