Pebble games for rigidity - TAU

Pebble games for rigidity - TAU

Pebble games for rigidity Overview Introduction The game of pebbling was first suggested by Lagarias and Saks, as a tool for solving a particular problem in number theory. The

algorithm can be used for analyzing the rigidity and flexibility of a variety of structures (mechanisms, molecules exc. ) Rigidity in 2D Bar and Joint Introduced by Jacobs & Hendrickson 1997 , based on Laman condition Laman

graph of n vertices (1970) The whole graph has exactly 2n 3 edges For all k, every k-vertex subgraph has at most 2k 3 edges The graph describes a minimally rigid systems of rods (edges) and joints (vertices) in the plane. What does Laman mean? For the whole

graph |e|+3=2|v| |e|=2|v|-3 Number of edges (constrains) For Trivial DOFs of a Number of body in 2D vertices x 2 DOFs of a point

in 2D The edges (constrains) subgraphs are well distributed |e|2|v|-3 Laman condition Taking Laman condition literally leads to exponential time complexity Every sub-graph must be tested for the number

of vertices vs. edges Alternate Laman condition: The edges in G are independent in 2D if and only if for each edge (a, b), the graph formed by quadrupling (a, b) has no induced subgraph of k nodes and >2k edges => Building the graph from sub-graph and

testing each new edge for independence leads to polynomial time complexity Example Lets take the 2D undirected graph and run pebble game in 2D Corresponds to 2D bar & joint floating framework Example Lets take a floating bar and joint framework in 2D

Each vertex is given two pebbles, corresponding to the two degrees of freedom of a point in 2D A vertex can use its pebbles to cover any two edges which are incident to that vertex. Starting point is arbitrary. Building directed graph We will build directed edges by extending independent sub-group Quadrupling each new edge to test

independence with the sub-group we already have Quadrupl e the edge Begin with a single vertex (clearly independent) Direct an edge move General direct an edge move If i and j are vertices with two pebbles on each (corresponding to independent constraint), add the edge ij (oriented toward j) and pick up one of the

pebbles from i. In case 2 pebbles cannot be found at the ends of that constraint after an exhaustive search, the constraint is redundant (and therefore can to be directed). Pebble slide move Pebble slide move If ij is an edge in the pebble game's graph and there is a on j, reverse ij and move the pebble from j to i. pebble

Result The algorithm ends when all the edges have been processed. Result : 3 pebbles (only trivial DOFs) Redundant edge What happens to over constraints ? example with SS :

Any edge that cant be directed corresponds to redundant constraint. This happens when the length between its end point is already set by other constrains. Inside the rigid region any edge can be redundant. DOF number The resulting number of pebbles after all edges were processed, gives the number of DOFs of the corresponding

mechanism. For floating mechanism there are 3 trivial DOFs => 3 remaining pebbles is an indicator for rigidity For grounded mechanism 0 pebbles indicate rigidity (edges linked to gnd vertices are directed in the end, with any free pebble) Actually this is the number of non preset vertices (that have pebbles = DOFs)

Partition to Assur graphs A directed cut defines a partition to Assur graphs. Algorithm summary Find a subset of independent edges. Use an incremental algorithm: pick an edge, test if its independent of the current subset. Alternate Laman theorem: The edges in G are independent in 2D if and only if for each edge (a, b), the graph formed by

quadrupling (a, b) has no induced subgraph of k nodes and >2k edges Grow a maximal set of independent edges one at a time. New edge is added if it is independent of existing set. Quadruple the new edge and test the Laman condition. If Laman failed, then output not rigid. If 2n-3 independent edges are found, then graph is rigid (n = number of vertices). Testing an edge for independence takes O(n) time: we do 3 depth-first search in a graph with O(n) edges. At most m edges will be tested. The total running time is O(nm)

Rigidity in 2D Body & Bar Body & Bar subgroup of Bar & Joint Graph representation: Every rigid body = vertex The rest are bars Laman for Body & Bar in 2D

Laman graph for this case: The whole graph has exactly 3n 3 edges For all k, every k-vertex subgraph has at most 3k 3 edges |e|+3=3|v| Number of edges

(constrains) Trivial DOFs of a Number of body in 2D vertices x 3 DOFs of a body in 2D Pebble game for Body & Bar 2D Every vertex is given 3 pebbles The condition to direct an edge is

to have 4 pebbles on the incident vertices The rest is the same (example follows) Example Bb 2D 4 1 1 Grounded body (vertex)

2 3 Grounded mechanism with 1 DOF Partition to Assur groups : 4 can be analyzed as stand alone (dyad) Rigidity in 3D Body and bar Introduced by Tay and Whiteley Vertices -> rigid bodies

Edges -> bars Hinge = 5 bars Laman graph for this case: The whole graph has exactly 6n 6 edges For all k, every k-vertex subgraph has at most 6k 6 edges Need edge

at least 7 pebbles to direct an Examples Minimally rigid Flexible with 1 DOF Thank You !

Recently Viewed Presentations

  • Chapter 17: Aldehydes and Ketones: Nucleophilic Addition to

    Chapter 17: Aldehydes and Ketones: Nucleophilic Addition to

    Chapter 17: Aldehydes and Ketones: Nucleophilic Addition to the Carbonyl Group 17.1: Nomenclature (please read) 17.2: Structure and Bonding: Carbonyl groups have a
  • A Theory of Semantic Relevance Exemplified through ...

    A Theory of Semantic Relevance Exemplified through ...

    The principle of pragmatic modulation: The context of a conditional depends on general knowledge in long-term memory and knowledge of the specific circumstances of its utterance. Johnson-Laird, Byrne (2002) Roughly, what is the relationship b/w the dyads (antecedent, consequent) of...
  • PC Support & Repair

    PC Support & Repair

    iPhone 6. Turn GPS On/Off. HTC One M8. Turn GPS on/off in settings. Drains battery if you have an app open & running that uses the GPS. Practice Project. On Android & iOS: Turn off/on screen rotation. Adjust screen brightness....
  • KEEPING YOUR TRAINED HEAD ABOVE WATER Nebraska State

    KEEPING YOUR TRAINED HEAD ABOVE WATER Nebraska State

    2 Week Phase 2 NPOT. Drug Tech Training. HOW WE ARE GOING TO HELP YOU ACHIEVE THAT VISION. HOW WE ARE GOING TO HELP YOU ACHIEVE THAT VISION. Motivational Interviewing. ... MRT SUD Levels One, Two and Three. HOW WE...
  • Production and Operations Management: Manufacturing and Services

    Production and Operations Management: Manufacturing and Services

    Cut-and-try Linear programming Transportation method All of the above None of the above End of Chapter 16 Chapter 16 Sales and Operations Planning The Aggregate Operations Plan Examples: Chase and Level strategies Sales and Operations Planning Activities Long-range planning Greater...
  • The Argumentative Essay - Weebly

    The Argumentative Essay - Weebly

    ARGUMENTATIVE ESSAY * * * * * * * * * * * * * * * ARGUMENTATION The aim of writing argumentative essays is to convince or persuade the reader. One attempts to change the reader's mind and convince...
  • OTAK KITA - E-Learning | Universitas AMIKOM Yogyakarta

    OTAK KITA - E-Learning | Universitas AMIKOM Yogyakarta

    Title: OTAK KITA Author: JonMMx 2000 Last modified by: User Created Date: 1/5/2003 3:28:53 PM Document presentation format: On-screen Show (4:3) Other titles
  • No Taxation Without Representation Americas Background Declaration of

    No Taxation Without Representation Americas Background Declaration of

    Miranda v. Arizona. says you must be informed of your rights or what you say cannot be used. The Bill of Rights. 5 th Amendment. 5. th - A person cannot be deprived of life, liberty, or property without "...