On Reconfiguring Tree Linkages : Trees can lock
Identifieur interne : 009B27 ( Main/Exploration ); précédent : 009B26; suivant : 009B28On Reconfiguring Tree Linkages : Trees can lock
Auteurs : Therese Biedl ; Erik Demaine ; Martin Demaine ; Sylvain Lazard ; Anna Lubiw ; Joseph O'Rourke ; Steve Robbins ; Ileana Streinu ; Godfried Toussaint ; Sue WhitesidesSource :
English descriptors
- KwdEn :
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.
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: 002C74
- to stream Crin, to step Curation: 002C74
- to stream Crin, to step Checkpoint: 001A73
- to stream Main, to step Merge: 00A107
- to stream Main, to step Curation: 009B27
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="279">On Reconfiguring Tree Linkages : Trees can lock</title>
</titleStmt>
<publicationStmt><idno type="RBID">CRIN:biedl00a</idno>
<date when="2000" year="2000">2000</date>
<idno type="wicri:Area/Crin/Corpus">002C74</idno>
<idno type="wicri:Area/Crin/Curation">002C74</idno>
<idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">002C74</idno>
<idno type="wicri:Area/Crin/Checkpoint">001A73</idno>
<idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">001A73</idno>
<idno type="wicri:Area/Main/Merge">00A107</idno>
<idno type="wicri:Area/Main/Curation">009B27</idno>
<idno type="wicri:Area/Main/Exploration">009B27</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="Therese" last="Biedl">Therese Biedl</name>
</author>
<author><name sortKey="Demaine, Erik" sort="Demaine, Erik" uniqKey="Demaine E" first="Erik" last="Demaine">Erik Demaine</name>
</author>
<author><name sortKey="Demaine, Martin" sort="Demaine, Martin" uniqKey="Demaine M" first="Martin" last="Demaine">Martin Demaine</name>
</author>
<author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name>
</author>
<author><name sortKey="Lubiw, Anna" sort="Lubiw, Anna" uniqKey="Lubiw A" first="Anna" last="Lubiw">Anna Lubiw</name>
</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>
</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>
</author>
<author><name sortKey="Whitesides, Sue" sort="Whitesides, Sue" uniqKey="Whitesides S" first="Sue" last="Whitesides">Sue Whitesides</name>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>linkages</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en" wicri:score="2583">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>
<affiliations><list></list>
<tree><noCountry><name sortKey="Biedl, Therese" sort="Biedl, Therese" uniqKey="Biedl T" first="Therese" last="Biedl">Therese Biedl</name>
<name sortKey="Demaine, Erik" sort="Demaine, Erik" uniqKey="Demaine E" first="Erik" last="Demaine">Erik Demaine</name>
<name sortKey="Demaine, Martin" sort="Demaine, Martin" uniqKey="Demaine M" first="Martin" last="Demaine">Martin Demaine</name>
<name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name>
<name sortKey="Lubiw, Anna" sort="Lubiw, Anna" uniqKey="Lubiw A" first="Anna" last="Lubiw">Anna Lubiw</name>
<name sortKey="O Rourke, Joseph" sort="O Rourke, Joseph" uniqKey="O Rourke J" first="Joseph" last="O'Rourke">Joseph O'Rourke</name>
<name sortKey="Robbins, Steve" sort="Robbins, Steve" uniqKey="Robbins S" first="Steve" last="Robbins">Steve Robbins</name>
<name sortKey="Streinu, Ileana" sort="Streinu, Ileana" uniqKey="Streinu I" first="Ileana" last="Streinu">Ileana Streinu</name>
<name sortKey="Toussaint, Godfried" sort="Toussaint, Godfried" uniqKey="Toussaint G" first="Godfried" last="Toussaint">Godfried Toussaint</name>
<name sortKey="Whitesides, Sue" sort="Whitesides, Sue" uniqKey="Whitesides S" first="Sue" last="Whitesides">Sue Whitesides</name>
</noCountry>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 009B27 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 009B27 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Main |étape= Exploration |type= RBID |clé= CRIN:biedl00a |texte= On Reconfiguring Tree Linkages : Trees can lock }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |