A Note on Reconfiguring Tree Linkages: Trees can Lock
| Autor: | Martin L. Demaine, Steve Robbins, Anna Lubiw, Ileana Streinu, Joseph O'Rourke, Godfried T. Toussaint, Erik D. Demaine, Sue Whitesides, Sylvain Lazard, Therese C. Biedl |
|---|---|
| Přispěvatelé: | Department of Computer Science [Calgary] (CPSC), University of Calgary, Models, algorithms and geometry for computer graphics and vision (ISA), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), School of computer science [Ottawa] (SCS), Carleton University |
| Jazyk: | angličtina |
| Rok vydání: | 2002 |
| Předmět: |
K-ary tree
Record locking [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] Motion (geometry) ComputerApplications_COMPUTERSINOTHERSYSTEMS 0102 computer and information sciences 02 engineering and technology Computer Science::Computational Geometry 01 natural sciences Combinatorics 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics planification de trajectoires distance geometry Computer Science::Databases Mathematics graph embedding Plane (geometry) Applied Mathematics Regular polygon motion planning linkage reconfiguration tree embedding Tree (graph theory) reconfiguration de mécanismes articulés 010201 computation theory & mathematics Polygonal chain Polygon 020201 artificial intelligence & image processing |
| Zdroj: | Discrete Applied Mathematics Discrete Applied Mathematics, 2002, 117 (1-3), pp.293-297. ⟨10.1016/S0166-218X(01)00229-3⟩ Discrete Applied Mathematics, Elsevier, 2002, 117 (1-3), pp.293-297. ⟨10.1016/S0166-218X(01)00229-3⟩ |
| ISSN: | 0166-218X |
| DOI: | 10.1016/S0166-218X(01)00229-3⟩ |
| Popis: | Article dans revue scientifique avec comité de lecture.; It has recently been shown that any polygonal chain in the plane can be reconfigured to lie on a straight line, and any polygon can be reconfigured to be convex. This result cannot be extended to tree linkages: we show that there are trees with two configurations that are not connected by a motion. Indeed, we prove that an $N$-link tree can have $2^{Omega(N)}$ equivalence classes of configurations. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect