Flat-state connectivity of linkages under dihedral motions

Greg Aloupis; Erik D. Demaine; Vida Dujmović; Jeff Erickson; Stefan Langerman; Henk Meijer; Joseph O'Rourke; Mark Overmars; Michael Soss; Ileana Streinu; Godfried T. Toussaint

doi:10.1007/3-540-36136-7_33

Flat-state connectivity of linkages under dihedral motions

Greg Aloupis, Erik D. Demaine, Vida Dujmović, Jeff Erickson, Stefan Langerman, Henk Meijer, Joseph O'Rourke, Mark Overmars, Michael Soss, Ileana Streinu, Godfried T. Toussaint

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We explore which classes of linkages have the property that each pair of their flat states - that is, their embeddings in ℝ² 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 restrictedclasses of linkages. Many open problems are posed.

Original language	English (US)
Title of host publication	Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings
Pages	369-380
Number of pages	12
DOIs	https://doi.org/10.1007/3-540-36136-7_33
State	Published - 2002
Event	13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 - Vancouver, BC, Canada Duration: Nov 21 2002 → Nov 23 2002

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2518 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
Country/Territory	Canada
City	Vancouver, BC
Period	11/21/02 → 11/23/02

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-36136-7_33

Cite this

Aloupis, G., Demaine, E. D., Dujmović, V., Erickson, J., Langerman, S., Meijer, H., O'Rourke, J., Overmars, M., Soss, M., Streinu, I., & Toussaint, G. T. (2002). Flat-state connectivity of linkages under dihedral motions. In Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings (pp. 369-380). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2518 LNCS). https://doi.org/10.1007/3-540-36136-7_33

Flat-state connectivity of linkages under dihedral motions. / Aloupis, Greg; Demaine, Erik D.; Dujmović, Vida et al.
Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. 2002. p. 369-380 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2518 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Aloupis, G, Demaine, ED, Dujmović, V, Erickson, J, Langerman, S, Meijer, H, O'Rourke, J, Overmars, M, Soss, M, Streinu, I & Toussaint, GT 2002, Flat-state connectivity of linkages under dihedral motions. in Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2518 LNCS, pp. 369-380, 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002, Vancouver, BC, Canada, 11/21/02. https://doi.org/10.1007/3-540-36136-7_33

Aloupis G, Demaine ED, Dujmović V, Erickson J, Langerman S, Meijer H et al. Flat-state connectivity of linkages under dihedral motions. In Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. 2002. p. 369-380. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-36136-7_33

@inproceedings{d928d4d15d4e4f418cedc87f327db4df,

title = "Flat-state connectivity of linkages under dihedral motions",

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 restrictedclasses of linkages. Many open problems are posed.",

author = "Greg Aloupis and Demaine, {Erik D.} and Vida Dujmovi{\'c} and Jeff Erickson and Stefan Langerman and Henk Meijer and Joseph O'Rourke and Mark Overmars and Michael Soss and Ileana Streinu and Toussaint, {Godfried T.}",

year = "2002",

doi = "10.1007/3-540-36136-7_33",

language = "English (US)",

isbn = "3540001425",

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

pages = "369--380",

booktitle = "Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings",

}

TY - GEN

T1 - Flat-state connectivity of linkages under dihedral motions

AU - Aloupis, Greg

AU - Demaine, Erik D.

AU - Dujmović, Vida

AU - Erickson, Jeff

AU - Langerman, Stefan

AU - Meijer, Henk

AU - O'Rourke, Joseph

AU - Overmars, Mark

AU - Soss, Michael

AU - Streinu, Ileana

AU - Toussaint, Godfried T.

PY - 2002

Y1 - 2002

N2 - 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 restrictedclasses of linkages. Many open problems are posed.

AB - 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 restrictedclasses of linkages. Many open problems are posed.

UR - http://www.scopus.com/inward/record.url?scp=84878659823&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84878659823&partnerID=8YFLogxK

U2 - 10.1007/3-540-36136-7_33

DO - 10.1007/3-540-36136-7_33

M3 - Conference contribution

AN - SCOPUS:84878659823

SN - 3540001425

SN - 9783540001423

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 369

EP - 380

BT - Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings

T2 - 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002

Y2 - 21 November 2002 through 23 November 2002

ER -

Flat-state connectivity of linkages under dihedral motions

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this