Abstract
We explore which classes of linkages have the property that each pair of their flat states—that is, their embeddings in ℝ2 without self-intersection—can be connected by a continuous dihedral motion that avoids self-intersection throughout. Dihedral motions preserve all angles between pairs of incident edges, which is most natural for protein models. Our positive results include proofs that open chains with nonacute angles are flat-state connected, as are closed orthogonal unit-length chains. Among our negative results is an example of an orthogonal graph linkage that is flat-state disconnected. Several additional results are obtained for other restricted classes of linkages. Many open problems are posed.
Research initiated at the 17th Winter Workshop on Computational Geometry, Bellairs Research Institute of McGill University, Feb. 1-8, 2002.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Oswin Aichholzer, Carmen Cortés, Erik D. Demaine, Vida Dujmović, Jeff Erickson, Henk Meijer, Mark Overmars, Belén Palop, Suneeta Ramaswami, and Godfried T. Toussaint. Flipturning polygons. In Proc. Japan Conf. Discrete Comput. Geom., Lecture Notes in Computer Science, Tokyo, Japan, November 2000. To appear in Discrete Comput. Geom.
Greg Aloupis, Erik D. Demaine, Henk Meijer, Joseph O’Rourke, Ileana Streinu, and Godfried Toussaint. Flat-state connectedness of fixed-angle chains: Special acute chains. In Proc. 14th Canad. Conf. Comput. Geom., August 2002.
T. Biedl, E. Demaine, M. Demaine, S. Lazard, A. Lubiw, J. O’Rourke, M. Overmars, S. Robbins, I. Streinu, G. Toussaint, and S. Whitesides. Locked and unlocked polygonal chains in 3D. Discrete Comput. Geom., 26(3):269–282, 2001.
J. Cantarella and H. Johnston. Nontrivial embeddings of polygonal intervals and unknots in 3-space. J. Knot Theory Ramifications, 7:1027–1039, 1998.
R. Connelly, E. D. Demaine, and G. Rote. Straightening polygonal arcs and convexifying polygonal cycles. In Proc. 41st Annu. IEEE Sympos. Found. Comput. Sci., pages 432–442. IEEE, November 2000.
Maxim D. Frank-Kamenetskii. Unravelling DNA. Addison-Wesley, 1997.
M. Lal. Monte Carlo computer simulations of chain molecules. Molecular Physics, 17:57–64, 1969.
B. MacDonald, N. Jan, D. L. Hunter, and M. O. Steinitz. Polymer conformations through wiggling. Journal of Physics A: Mathematical and General Physics, 18:2627–2631, 1985.
N. Madras, A. Orlitsky, and L. A. Shepp. Monte Carlo generation of self-avoiding walks with fixed endpoints and fixed length. Journal of Statistical Physics, 58:159–183, 1990.
Neal Madras and Gordon Slade. The Self-Avoiding Walk. Birkháuser, 1993.
M. Soss and G. T. Toussaint. Geometric and computational aspects of polymer reconfiguration. J. Math. Chemistry, 27(4):303–318, 2000.
C. E. Soteros and S. G. Whittington. Polygons and stars in a slit geometry. Journal of Physics A: Mathematical and General Physics, 21:L857–L861, 1988.
I. Streinu. A combinatorial approach to planar non-colliding robot arm motion planning. In Proc. 41st Annu. IEEE Sympos. Found. Comput. Sci. IEEE, November 2000. 443–453.
G. T. Toussaint. The Erdós-Nagy theorem and its ramifications. In Proc. 11th Canad. Conf. Comput. Geom., pages 9–12, 1999.
S. G. Whittington. Self-avoiding walks with geometrical constraints. Journal of Statistical Physics, 30(2):449–456, 1983.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aloupis, G. et al. (2002). Flat-State Connectivity of Linkages under Dihedral Motions. In: Bose, P., Morin, P. (eds) Algorithms and Computation. ISAAC 2002. Lecture Notes in Computer Science, vol 2518. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36136-7_33
Download citation
DOI: https://doi.org/10.1007/3-540-36136-7_33
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00142-3
Online ISBN: 978-3-540-36136-7
eBook Packages: Springer Book Archive