Locked and Unlocked Polygonal Chains in Three Dimensions

Thérèse Biedl; Erik Demaine; Martin Demaine; Sylvain Lazard; Anna Lubiw; Joseph O'Rourke; M. Overmars; Steve Robbins; Ileana Streinu; Godfried Toussaint; Sue Whitesides

inria-00098772, version 2

Locked and Unlocked Polygonal Chains in Three Dimensions

Thérèse Biedl^a^, 1, Erik Demaine^a^, 1, Martin Demaine^a^, 1, Sylvain Lazard^b^, 2, Anna Lubiw^a^, 1, Joseph O'Rourke^c^, 3, M. Overmars^d^, 4, Steve Robbins^e^, 5, Ileana Streinu^f^, 3, Godfried Toussaint^e^, 5, Sue Whitesides^e^, 5

Symposium on Discrete Algorithms - SODA'99 (1999) 866 - 867

Résumé : This paper studies movements of polygonal chains in three dimensions whose links are not allowed to cross or change length. Our main result is an algorithmic proof that any simple closed chain that initially takes the form of a planar polygon can be made convex in three dimensions. Other results include an algorithm for straightening open chains having a simple orthogonal projection onto some plane, and an algorithm for making convex any open chain initially configured on the surface of a polytope. All our algorithms require only O(n) basic ``moves.''

a – UNIVERSITY OF WATERLOO
b – INRIA
c – SMITH COLLEGE
d – UTRECHT UNIVERSITY
e – MCGILL UNIVERSITY
f – Department of Computer Science
1 : University of Waterloo (Department of Physics)
University of Waterloo
2 : ISA (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
3 : Department of Computer Science
Smith College
4 : Departments of Psychonomics, and Media and Communication, Utrecht University (UTRECHT UNIVERSITY)
Aucune
5 : McGill University (McGill)
McGill University

inria-00098772, version 2
http://hal.inria.fr/inria-00098772
oai:hal.inria.fr:inria-00098772
Contributeur : Sylvain Lazard <>
Soumis le : Vendredi 19 Novembre 2010, 14:12:10
Dernière modification le : Lundi 22 Novembre 2010, 16:59:13

Voir la fiche détaillée

Documents associés

PDF :

Texte intégral chez l'éditeur

Voir aussi

Exporter

Bibtex EndNote TEI RefWorks

%F inria-00098772, version 2
%0 Conference Proceedings
%U http://hal.inria.fr/inria-00098772
%2 INFO:INFO_OH
%T Locked and Unlocked Polygonal Chains in Three Dimensions
%A Biedl, Thérèse
%A Demaine, Erik
%A Demaine, Martin
%A Lazard, Sylvain
%A Lubiw, Anna
%A O'Rourke, Joseph
%A Overmars, M.
%A Robbins, Steve
%A Streinu, Ileana
%A Toussaint, Godfried
%A Whitesides, Sue
%+ University of Waterloo - Department of Physics , ISA - INRIA Lorraine - LORIA , Department of Computer Science , Departments of Psychonomics, and Media and Communication, Utrecht University - UTRECHT UNIVERSITY , McGill University - McGill
%X This paper studies movements of polygonal chains in three dimensions whose links are not allowed to cross or change length. Our main result is an algorithmic proof that any simple closed chain that initially takes the form of a planar polygon can be made convex in three dimensions. Other results include an algorithm for straightening open chains having a simple orthogonal projection onto some plane, and an algorithm for making convex any open chain initially configured on the surface of a polytope. All our algorithms require only O(n) basic ``moves.''
%2 G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.0: General, F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems
%G Anglais
%8 1999-00-00
%2 internationale
%B Symposium on Discrete Algorithms - SODA'99
%2 Baltimore
%2 États-Unis
%8 1999-01-17
%8 1999-01-19
%I ACM-SIAM
%2 SODA '99 Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms
%P 866 - 867
%2 http://delivery.acm.org/10.1145/320000/314977/p866-biedl.pdf?key1=314977&key2=9974440921&coll=DL&dl=ACM&CFID=115354797&CFTOKEN=35617922
%2 http://portal.acm.org/citation.cfm?id=314500.314977&coll=portal&dl=ACM&type=series&idx=SERIES422&part=series&WantType=Proceedings&title=SODA&CFID=69382355&CFTOKEN=57562847
%K linkages || mécanismes articulés
%Z ISBN: 0-89871-434-6
%Z A01-R-188 || biedl01a

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Communications avec actes</head>
<biblStruct type="inproceedings" xml:id="inria-00098772"><analytic>
<author><persName><forename>Thérèse</forename><surname>Biedl</surname></persName>
<affiliation>
<orgName type="laboratory">Department of Physics</orgName>
<orgName type="team">University of Waterloo</orgName>
<country>FR</country>
<orgName type="institution">University of Waterloo</orgName>
</affiliation>
</author>
<author><persName><forename>Erik</forename><surname>Demaine</surname></persName>
<affiliation>
<orgName type="laboratory">Department of Physics</orgName>
<orgName type="team">University of Waterloo</orgName>
<country>FR</country>
<orgName type="institution">University of Waterloo</orgName>
</affiliation>
</author>
<author><persName><forename>Martin</forename><surname>Demaine</surname></persName>
<affiliation>
<orgName type="laboratory">Department of Physics</orgName>
<orgName type="team">University of Waterloo</orgName>
<country>FR</country>
<orgName type="institution">University of Waterloo</orgName>
</affiliation>
</author>
<author><persName><forename>Sylvain</forename><surname>Lazard</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">ISA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Anna</forename><surname>Lubiw</surname></persName>
<affiliation>
<orgName type="laboratory">Department of Physics</orgName>
<orgName type="team">University of Waterloo</orgName>
<country>FR</country>
<orgName type="institution">University of Waterloo</orgName>
</affiliation>
</author>
<author><persName><forename>Joseph</forename><surname>O'Rourke</surname></persName>
<affiliation>
<orgName type="team">Department of Computer Science</orgName>
<country>US</country>
<orgName type="institution">Smith College</orgName>
</affiliation>
</author>
<author><persName><forename>M.</forename><surname>Overmars</surname></persName>
<affiliation>
<orgName type="laboratory">UTRECHT UNIVERSITY</orgName>
<orgName type="team">Departments of Psychonomics, and Media and Communication, Utrecht University</orgName>
<country>FR</country>
<orgName type="institution">Aucune</orgName>
</affiliation>
</author>
<author><persName><forename>Steve</forename><surname>Robbins</surname></persName>
<affiliation>
<orgName type="laboratory">McGill</orgName>
<orgName type="team">McGill University</orgName>
<country>CA</country>
<orgName type="institution">McGill University</orgName>
</affiliation>
</author>
<author><persName><forename>Ileana</forename><surname>Streinu</surname></persName>
<affiliation>
<orgName type="team">Department of Computer Science</orgName>
<country>US</country>
<orgName type="institution">Smith College</orgName>
</affiliation>
</author>
<author><persName><forename>Godfried</forename><surname>Toussaint</surname></persName>
<affiliation>
<orgName type="laboratory">McGill</orgName>
<orgName type="team">McGill University</orgName>
<country>CA</country>
<orgName type="institution">McGill University</orgName>
</affiliation>
</author>
<author><persName><forename>Sue</forename><surname>Whitesides</surname></persName>
<affiliation>
<orgName type="laboratory">McGill</orgName>
<orgName type="team">McGill University</orgName>
<country>CA</country>
<orgName type="institution">McGill University</orgName>
</affiliation>
</author>
<title type="main" level="a">Locked and Unlocked Polygonal Chains in Three Dimensions</title></analytic><monogr><meeting>Symposium on Discrete Algorithms - SODA'99</meeting><imprint><publisher>ACM-SIAM</publisher><pubPlace><settlement>Baltimore</settlement><country>États-Unis</country></pubPlace><biblScope type="publicationDate">1999-00-00</biblScope><biblScope type="pp">866 - 867</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00098772</idno><idno type="HALFile">http://hal.inria.fr/inria-00098772/PDF/99-R-227.pdf</idno></biblStruct>
</listBibl>
</listBibl>