On Reconfiguring Tree Linkages: Trees can lock
Identifieur interne : 003698 ( Hal/Curation ); précédent : 003697; suivant : 003699On Reconfiguring Tree Linkages: Trees can lock
Auteurs : Thérèse Biedl [Canada] ; Erik Demaine [Canada] ; Martin Demaine [Canada] ; Sylvain Lazard [France] ; Anna Lubiw [Canada] ; Joseph O'Rourke ; Steve Robbins [Canada] ; Ileana Streinu ; Godfried Toussaint [Canada] ; Sue Whitesides [Canada]Source :
Descripteurs français
- mix :
Abstract
It has recently been shown that any simple (i.e. nonintersecting) polygonal chain in the plane can be reconfigured to lie on a straight line, and any simple polygon can be reconfigured to be convex. This result cannot be extended to tree linkages: we show that there are trees with two simple configurations that are not connected by a motion that preserves simplicity throughout the motion. Indeed, we prove that an $N$-link tree can have $2^{\Omega(N)}$ equivalence classes of configurations.
Url:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: Pour aller vers cette notice dans l'étape Curation :003698
Links to Exploration step
Hal:inria-00099329Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">On Reconfiguring Tree Linkages: Trees can lock</title><author><name sortKey="Biedl, Therese" sort="Biedl, Therese" uniqKey="Biedl T" first="Thérèse" last="Biedl">Thérèse Biedl</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-82231" status="VALID"><orgName>Department of Computer Science [Calgary]</orgName><orgName type="acronym">CPSC</orgName><desc><address><addrLine>University of Calgary 2500 University Dr. NW Calgary, Alberta Canada T2N 1N4</addrLine><country key="CA"></country></address><ref type="url">http://www.cpsc.ucalgary.ca/</ref></desc><listRelation><relation active="#struct-106219" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-106219" type="direct"><org type="institution" xml:id="struct-106219" status="VALID"><orgName>University of Calgary</orgName><desc><address><addrLine>2500 University Dr NW Calgary, Alberta, T2N 1N4</addrLine><country key="CA"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country><placeName><settlement type="city">Calgary</settlement><region type="state">Alberta</region></placeName><orgName type="university">Université de Calgary</orgName></affiliation></author><author><name sortKey="Demaine, Erik" sort="Demaine, Erik" uniqKey="Demaine E" first="Erik" last="Demaine">Erik Demaine</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-82231" status="VALID"><orgName>Department of Computer Science [Calgary]</orgName><orgName type="acronym">CPSC</orgName><desc><address><addrLine>University of Calgary 2500 University Dr. NW Calgary, Alberta Canada T2N 1N4</addrLine><country key="CA"></country></address><ref type="url">http://www.cpsc.ucalgary.ca/</ref></desc><listRelation><relation active="#struct-106219" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-106219" type="direct"><org type="institution" xml:id="struct-106219" status="VALID"><orgName>University of Calgary</orgName><desc><address><addrLine>2500 University Dr NW Calgary, Alberta, T2N 1N4</addrLine><country key="CA"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country><placeName><settlement type="city">Calgary</settlement><region type="state">Alberta</region></placeName><orgName type="university">Université de Calgary</orgName></affiliation></author><author><name sortKey="Demaine, Martin" sort="Demaine, Martin" uniqKey="Demaine M" first="Martin" last="Demaine">Martin Demaine</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-82231" status="VALID"><orgName>Department of Computer Science [Calgary]</orgName><orgName type="acronym">CPSC</orgName><desc><address><addrLine>University of Calgary 2500 University Dr. NW Calgary, Alberta Canada T2N 1N4</addrLine><country key="CA"></country></address><ref type="url">http://www.cpsc.ucalgary.ca/</ref></desc><listRelation><relation active="#struct-106219" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-106219" type="direct"><org type="institution" xml:id="struct-106219" status="VALID"><orgName>University of Calgary</orgName><desc><address><addrLine>2500 University Dr NW Calgary, Alberta, T2N 1N4</addrLine><country key="CA"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country><placeName><settlement type="city">Calgary</settlement><region type="state">Alberta</region></placeName><orgName type="university">Université de Calgary</orgName></affiliation></author><author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2350" status="OLD"><idno type="RNSR">199521440F</idno><orgName>Models, algorithms and geometry for computer graphics and vision</orgName><orgName type="acronym">ISA</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/isa</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Lubiw, Anna" sort="Lubiw, Anna" uniqKey="Lubiw A" first="Anna" last="Lubiw">Anna Lubiw</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-82231" status="VALID"><orgName>Department of Computer Science [Calgary]</orgName><orgName type="acronym">CPSC</orgName><desc><address><addrLine>University of Calgary 2500 University Dr. NW Calgary, Alberta Canada T2N 1N4</addrLine><country key="CA"></country></address><ref type="url">http://www.cpsc.ucalgary.ca/</ref></desc><listRelation><relation active="#struct-106219" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-106219" type="direct"><org type="institution" xml:id="struct-106219" status="VALID"><orgName>University of Calgary</orgName><desc><address><addrLine>2500 University Dr NW Calgary, Alberta, T2N 1N4</addrLine><country key="CA"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country><placeName><settlement type="city">Calgary</settlement><region type="state">Alberta</region></placeName><orgName type="university">Université de Calgary</orgName></affiliation></author><author><name sortKey="O Rourke, Joseph" sort="O Rourke, Joseph" uniqKey="O Rourke J" first="Joseph" last="O'Rourke">Joseph O'Rourke</name></author><author><name sortKey="Robbins, Steve" sort="Robbins, Steve" uniqKey="Robbins S" first="Steve" last="Robbins">Steve Robbins</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-14804" status="VALID"><orgName>School of computer science [Ottawa]</orgName><orgName type="acronym">SCS</orgName><desc><address><addrLine>Herzberg Building 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.scs.carleton.ca/school/</ref></desc><listRelation><relation active="#struct-208909" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-208909" type="direct"><org type="institution" xml:id="struct-208909" status="VALID"><orgName>Carleton University</orgName><desc><address><addrLine>1125 Colonel By Drive Ottawa, ON, Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.carleton.ca/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Streinu, Ileana" sort="Streinu, Ileana" uniqKey="Streinu I" first="Ileana" last="Streinu">Ileana Streinu</name></author><author><name sortKey="Toussaint, Godfried" sort="Toussaint, Godfried" uniqKey="Toussaint G" first="Godfried" last="Toussaint">Godfried Toussaint</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-14804" status="VALID"><orgName>School of computer science [Ottawa]</orgName><orgName type="acronym">SCS</orgName><desc><address><addrLine>Herzberg Building 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.scs.carleton.ca/school/</ref></desc><listRelation><relation active="#struct-208909" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-208909" type="direct"><org type="institution" xml:id="struct-208909" status="VALID"><orgName>Carleton University</orgName><desc><address><addrLine>1125 Colonel By Drive Ottawa, ON, Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.carleton.ca/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Whitesides, Sue" sort="Whitesides, Sue" uniqKey="Whitesides S" first="Sue" last="Whitesides">Sue Whitesides</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-14804" status="VALID"><orgName>School of computer science [Ottawa]</orgName><orgName type="acronym">SCS</orgName><desc><address><addrLine>Herzberg Building 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.scs.carleton.ca/school/</ref></desc><listRelation><relation active="#struct-208909" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-208909" type="direct"><org type="institution" xml:id="struct-208909" status="VALID"><orgName>Carleton University</orgName><desc><address><addrLine>1125 Colonel By Drive Ottawa, ON, Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.carleton.ca/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00099329</idno><idno type="halId">inria-00099329</idno><idno type="halUri">https://hal.inria.fr/inria-00099329</idno><idno type="url">https://hal.inria.fr/inria-00099329</idno><date when="2000">2000</date><idno type="wicri:Area/Hal/Corpus">003698</idno><idno type="wicri:Area/Hal/Curation">003698</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">On Reconfiguring Tree Linkages: Trees can lock</title><author><name sortKey="Biedl, Therese" sort="Biedl, Therese" uniqKey="Biedl T" first="Thérèse" last="Biedl">Thérèse Biedl</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-82231" status="VALID"><orgName>Department of Computer Science [Calgary]</orgName><orgName type="acronym">CPSC</orgName><desc><address><addrLine>University of Calgary 2500 University Dr. NW Calgary, Alberta Canada T2N 1N4</addrLine><country key="CA"></country></address><ref type="url">http://www.cpsc.ucalgary.ca/</ref></desc><listRelation><relation active="#struct-106219" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-106219" type="direct"><org type="institution" xml:id="struct-106219" status="VALID"><orgName>University of Calgary</orgName><desc><address><addrLine>2500 University Dr NW Calgary, Alberta, T2N 1N4</addrLine><country key="CA"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country><placeName><settlement type="city">Calgary</settlement><region type="state">Alberta</region></placeName><orgName type="university">Université de Calgary</orgName></affiliation></author><author><name sortKey="Demaine, Erik" sort="Demaine, Erik" uniqKey="Demaine E" first="Erik" last="Demaine">Erik Demaine</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-82231" status="VALID"><orgName>Department of Computer Science [Calgary]</orgName><orgName type="acronym">CPSC</orgName><desc><address><addrLine>University of Calgary 2500 University Dr. NW Calgary, Alberta Canada T2N 1N4</addrLine><country key="CA"></country></address><ref type="url">http://www.cpsc.ucalgary.ca/</ref></desc><listRelation><relation active="#struct-106219" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-106219" type="direct"><org type="institution" xml:id="struct-106219" status="VALID"><orgName>University of Calgary</orgName><desc><address><addrLine>2500 University Dr NW Calgary, Alberta, T2N 1N4</addrLine><country key="CA"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country><placeName><settlement type="city">Calgary</settlement><region type="state">Alberta</region></placeName><orgName type="university">Université de Calgary</orgName></affiliation></author><author><name sortKey="Demaine, Martin" sort="Demaine, Martin" uniqKey="Demaine M" first="Martin" last="Demaine">Martin Demaine</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-82231" status="VALID"><orgName>Department of Computer Science [Calgary]</orgName><orgName type="acronym">CPSC</orgName><desc><address><addrLine>University of Calgary 2500 University Dr. NW Calgary, Alberta Canada T2N 1N4</addrLine><country key="CA"></country></address><ref type="url">http://www.cpsc.ucalgary.ca/</ref></desc><listRelation><relation active="#struct-106219" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-106219" type="direct"><org type="institution" xml:id="struct-106219" status="VALID"><orgName>University of Calgary</orgName><desc><address><addrLine>2500 University Dr NW Calgary, Alberta, T2N 1N4</addrLine><country key="CA"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country><placeName><settlement type="city">Calgary</settlement><region type="state">Alberta</region></placeName><orgName type="university">Université de Calgary</orgName></affiliation></author><author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2350" status="OLD"><idno type="RNSR">199521440F</idno><orgName>Models, algorithms and geometry for computer graphics and vision</orgName><orgName type="acronym">ISA</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/isa</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Lubiw, Anna" sort="Lubiw, Anna" uniqKey="Lubiw A" first="Anna" last="Lubiw">Anna Lubiw</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-82231" status="VALID"><orgName>Department of Computer Science [Calgary]</orgName><orgName type="acronym">CPSC</orgName><desc><address><addrLine>University of Calgary 2500 University Dr. NW Calgary, Alberta Canada T2N 1N4</addrLine><country key="CA"></country></address><ref type="url">http://www.cpsc.ucalgary.ca/</ref></desc><listRelation><relation active="#struct-106219" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-106219" type="direct"><org type="institution" xml:id="struct-106219" status="VALID"><orgName>University of Calgary</orgName><desc><address><addrLine>2500 University Dr NW Calgary, Alberta, T2N 1N4</addrLine><country key="CA"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country><placeName><settlement type="city">Calgary</settlement><region type="state">Alberta</region></placeName><orgName type="university">Université de Calgary</orgName></affiliation></author><author><name sortKey="O Rourke, Joseph" sort="O Rourke, Joseph" uniqKey="O Rourke J" first="Joseph" last="O'Rourke">Joseph O'Rourke</name></author><author><name sortKey="Robbins, Steve" sort="Robbins, Steve" uniqKey="Robbins S" first="Steve" last="Robbins">Steve Robbins</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-14804" status="VALID"><orgName>School of computer science [Ottawa]</orgName><orgName type="acronym">SCS</orgName><desc><address><addrLine>Herzberg Building 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.scs.carleton.ca/school/</ref></desc><listRelation><relation active="#struct-208909" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-208909" type="direct"><org type="institution" xml:id="struct-208909" status="VALID"><orgName>Carleton University</orgName><desc><address><addrLine>1125 Colonel By Drive Ottawa, ON, Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.carleton.ca/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Streinu, Ileana" sort="Streinu, Ileana" uniqKey="Streinu I" first="Ileana" last="Streinu">Ileana Streinu</name></author><author><name sortKey="Toussaint, Godfried" sort="Toussaint, Godfried" uniqKey="Toussaint G" first="Godfried" last="Toussaint">Godfried Toussaint</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-14804" status="VALID"><orgName>School of computer science [Ottawa]</orgName><orgName type="acronym">SCS</orgName><desc><address><addrLine>Herzberg Building 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.scs.carleton.ca/school/</ref></desc><listRelation><relation active="#struct-208909" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-208909" type="direct"><org type="institution" xml:id="struct-208909" status="VALID"><orgName>Carleton University</orgName><desc><address><addrLine>1125 Colonel By Drive Ottawa, ON, Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.carleton.ca/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Whitesides, Sue" sort="Whitesides, Sue" uniqKey="Whitesides S" first="Sue" last="Whitesides">Sue Whitesides</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-14804" status="VALID"><orgName>School of computer science [Ottawa]</orgName><orgName type="acronym">SCS</orgName><desc><address><addrLine>Herzberg Building 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.scs.carleton.ca/school/</ref></desc><listRelation><relation active="#struct-208909" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-208909" type="direct"><org type="institution" xml:id="struct-208909" status="VALID"><orgName>Carleton University</orgName><desc><address><addrLine>1125 Colonel By Drive Ottawa, ON, Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.carleton.ca/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="fr"><term>linkages</term><term>mécanismes articulés</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">It has recently been shown that any simple (i.e. nonintersecting) polygonal chain in the plane can be reconfigured to lie on a straight line, and any simple polygon can be reconfigured to be convex. This result cannot be extended to tree linkages: we show that there are trees with two simple configurations that are not connected by a motion that preserves simplicity throughout the motion. Indeed, we prove that an $N$-link tree can have $2^{\Omega(N)}$ equivalence classes of configurations.</div></front></TEI><hal api="V3"><titleStmt><title xml:lang="en">On Reconfiguring Tree Linkages: Trees can lock</title><author role="aut"><persName><forename type="first">Thérèse</forename><surname>Biedl</surname></persName><email></email><idno type="halauthor">130502</idno><orgName ref="#struct-364709"></orgName><affiliation ref="#struct-82231"></affiliation></author><author role="aut"><persName><forename type="first">Erik</forename><surname>Demaine</surname></persName><email></email><idno type="halauthor">130503</idno><orgName ref="#struct-364709"></orgName><affiliation ref="#struct-82231"></affiliation></author><author role="aut"><persName><forename type="first">Martin</forename><surname>Demaine</surname></persName><email></email><idno type="halauthor">130504</idno><orgName ref="#struct-364709"></orgName><affiliation ref="#struct-82231"></affiliation></author><author role="aut"><persName><forename type="first">Sylvain</forename><surname>Lazard</surname></persName><email>sylvain.lazard@inria.fr</email><ptr type="url" target="http://www.loria.fr/~lazard/"></ptr><idno type="idhal">sylvain-lazard</idno><idno type="halauthor">661543</idno><affiliation ref="#struct-2350"></affiliation></author><author role="aut"><persName><forename type="first">Anna</forename><surname>Lubiw</surname></persName><email></email><idno type="halauthor">130505</idno><orgName ref="#struct-364709"></orgName><affiliation ref="#struct-82231"></affiliation></author><author role="aut"><persName><forename type="first">Joseph</forename><surname>O'Rourke</surname></persName><email></email><idno type="halauthor">130506</idno><orgName ref="#struct-364710"></orgName></author><author role="aut"><persName><forename type="first">Steve</forename><surname>Robbins</surname></persName><email></email><idno type="halauthor">130507</idno><orgName ref="#struct-134741"></orgName><affiliation ref="#struct-14804"></affiliation></author><author role="aut"><persName><forename type="first">Ileana</forename><surname>Streinu</surname></persName><email></email><idno type="halauthor">130508</idno><orgName ref="#struct-364710"></orgName></author><author role="aut"><persName><forename type="first">Godfried</forename><surname>Toussaint</surname></persName><email></email><idno type="halauthor">130509</idno><orgName ref="#struct-134741"></orgName><affiliation ref="#struct-14804"></affiliation></author><author role="aut"><persName><forename type="first">Sue</forename><surname>Whitesides</surname></persName><email></email><idno type="halauthor">130510</idno><orgName ref="#struct-134741"></orgName><affiliation ref="#struct-14804"></affiliation></author><editor role="depositor"><persName><forename>Sylvain</forename><surname>Lazard</surname></persName><email>sylvain.lazard@inria.fr</email></editor></titleStmt><editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2006-09-26 08:52:55</date><date type="whenModified">2016-05-19 01:09:32</date><date type="whenReleased">2006-09-28 15:22:46</date><date type="whenProduced">2000</date></edition><respStmt><resp>contributor</resp><name key="103314"><persName><forename>Sylvain</forename><surname>Lazard</surname></persName><email>sylvain.lazard@inria.fr</email></name></respStmt></editionStmt><publicationStmt><distributor>CCSD</distributor><idno type="halId">inria-00099329</idno><idno type="halUri">https://hal.inria.fr/inria-00099329</idno><idno type="halBibtex">biedl:inria-00099329</idno><idno type="halRefHtml">[Intern report] A00-R-388 || biedl00a, 2000, 16 p</idno><idno type="halRef">[Intern report] A00-R-388 || biedl00a, 2000, 16 p</idno></publicationStmt><seriesStmt><idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno><idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno><idno type="stamp" n="INPL">Institut National Polytechnique de Lorraine</idno><idno type="stamp" n="LORIA2">Publications du LORIA</idno><idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno><idno type="stamp" n="INRIA-NANCY-GRAND-EST">INRIA Nancy - Grand Est</idno><idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno><idno type="stamp" n="INRIA-LORRAINE">INRIA Nancy - Grand Est</idno><idno type="stamp" n="LABO-LORIA-SET" p="LORIA">LABO-LORIA-SET</idno></seriesStmt><notesStmt><note type="commentary">Rapport interne.</note><note type="audience" n="0">Not set</note><note type="report" n="3">Intern report</note></notesStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">On Reconfiguring Tree Linkages: Trees can lock</title><author role="aut"><persName><forename type="first">Thérèse</forename><surname>Biedl</surname></persName><idno type="halAuthorId">130502</idno><orgName ref="#struct-364709"></orgName><affiliation ref="#struct-82231"></affiliation></author><author role="aut"><persName><forename type="first">Erik</forename><surname>Demaine</surname></persName><idno type="halAuthorId">130503</idno><orgName ref="#struct-364709"></orgName><affiliation ref="#struct-82231"></affiliation></author><author role="aut"><persName><forename type="first">Martin</forename><surname>Demaine</surname></persName><idno type="halAuthorId">130504</idno><orgName ref="#struct-364709"></orgName><affiliation ref="#struct-82231"></affiliation></author><author role="aut"><persName><forename type="first">Sylvain</forename><surname>Lazard</surname></persName><email>sylvain.lazard@inria.fr</email><ptr type="url" target="http://www.loria.fr/~lazard/"></ptr><idno type="idHal">sylvain-lazard</idno><idno type="halAuthorId">661543</idno><affiliation ref="#struct-2350"></affiliation></author><author role="aut"><persName><forename type="first">Anna</forename><surname>Lubiw</surname></persName><idno type="halAuthorId">130505</idno><orgName ref="#struct-364709"></orgName><affiliation ref="#struct-82231"></affiliation></author><author role="aut"><persName><forename type="first">Joseph</forename><surname>O'Rourke</surname></persName><idno type="halAuthorId">130506</idno><orgName ref="#struct-364710"></orgName></author><author role="aut"><persName><forename type="first">Steve</forename><surname>Robbins</surname></persName><idno type="halAuthorId">130507</idno><orgName ref="#struct-134741"></orgName><affiliation ref="#struct-14804"></affiliation></author><author role="aut"><persName><forename type="first">Ileana</forename><surname>Streinu</surname></persName><idno type="halAuthorId">130508</idno><orgName ref="#struct-364710"></orgName></author><author role="aut"><persName><forename type="first">Godfried</forename><surname>Toussaint</surname></persName><idno type="halAuthorId">130509</idno><orgName ref="#struct-134741"></orgName><affiliation ref="#struct-14804"></affiliation></author><author role="aut"><persName><forename type="first">Sue</forename><surname>Whitesides</surname></persName><idno type="halAuthorId">130510</idno><orgName ref="#struct-134741"></orgName><affiliation ref="#struct-14804"></affiliation></author></analytic><monogr><idno type="reportNumber">A00-R-388 || biedl00a</idno><imprint><biblScope unit="pp">16 p</biblScope><date type="datePub">2000</date></imprint></monogr></biblStruct></sourceDesc><profileDesc><langUsage><language ident="en">English</language></langUsage><textClass><keywords scheme="author"><term xml:lang="fr">mécanismes articulés</term><term xml:lang="fr">linkages</term></keywords><classCode scheme="halDomain" n="info.info-oh">Computer Science [cs]/Other [cs.OH]</classCode><classCode scheme="halTypology" n="REPORT">Reports</classCode></textClass><abstract xml:lang="en">It has recently been shown that any simple (i.e. nonintersecting) polygonal chain in the plane can be reconfigured to lie on a straight line, and any simple polygon can be reconfigured to be convex. This result cannot be extended to tree linkages: we show that there are trees with two simple configurations that are not connected by a motion that preserves simplicity throughout the motion. Indeed, we prove that an $N$-link tree can have $2^{\Omega(N)}$ equivalence classes of configurations.</abstract></profileDesc></hal></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003698 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Curation/biblio.hfd -nk 003698 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Hal
|étape= Curation
|type= RBID
|clé= Hal:inria-00099329
|texte= On Reconfiguring Tree Linkages: Trees can lock
}}
| This area was generated with Dilib version V0.6.33. |  |