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. |  |