cse590 Information Processing in Sensor Networks Lecture 3 Rigidity Theory Lecturer Jie Gao 1 Scribe Amitabh Basu Overview of the Lecture In this lecture we looked at important results in rigidity theory Given a set of fixed length bars connected by hinges rigidity theory studies whether one can deform the shape continuously Some of the main results in rigidity theory are presented in this lecture In particular combinatorial rigidity of graphs and the pebble game for testing rigidity of graphs are discussed In the following sections we develop the theory in greater detail 2 Definitions A graph G V E consists of a set V of vertices and a set E of edges with V n E m Define a configuration P V to be an assignment of the vertices V to points in Rd In this class we focus on R2 A configuration is called generic if the coordinates are algebraically independent over the rational Intuitively speaking a generic configuration has no degeneracy i e no three points staying on the same line no three lines go through the same point etc The study of generic configurations are important because in practice we can assume that the sensor locations are generic A framework G P refers to a graph G along with a configuration A particular graph can have different frameworks with different edge lengths A framework is called flexible if there exists a continuous deformation from the given configuration to another such that edge lengths are preserved If no such deformation exists then it is called rigid See Figure 1 b d c a b c a d i ii b b a c c a d d iii iv Figure 1 i Rigid but not globally rigid ii Rigid but not globally rigid iii Globally rigid iv Flexible A configuration P p1 p2 pn can be represented by a point in R2n namely 2 variables for each point pi We define the configuration space C L with respect to edge length constraints L ij as the collections of configurations that satisfy the edge length constraints L Thus C L is a subspace of R2n 3 1 Many questions regarding a framework can be formulated as questions on the configuration space For example whether there is a realization of a graph with distance constraints L is to ask whether C L is empty The degree of freedom of a framework is actually the dimension of the configuration space C L If the configuration space has 0 dimension then the framework is rigid If C L has only one point then the framework is globally rigid A rigid framework is minimally rigid if it becomes flexible after an edge is removed A rigid framework is redundantly rigid if it remains rigid upon the removal of any edge Generally questions about the configuration space are hard to answer They are usually dealt by computational algebraic geometry or topology However the tangent space of C L is relatively more tractable The next section illustrates the important results regarding the tangent space 3 Infinitesimal Motion and Infinitesimal Rigidity Infinitesimal rigidity is defined over the tangent space In particular the configuration space of a framework is represented by C pi R2 pi pj pi pj 2ij ij E 1 Now we take the derivative at the configuration point p1 p2 pn We have the following equation pi pj pi pj 0 ij E 2 We define an infinitesimal motion v v1 v2 vn as a vector that satisfies the linear system in 2 We usually factor out the global rigid motion translation and rotation by pinning down an edge So we include the pin down equations vi vj 0 for an edge ij in the graph This linear system 2 with the pin down equations always has a trivial solution v 0 If it has a non trivial solution the infinitesimal motion is called non trivial A framework is infinitesimally flexible if it has a non trivial infinitesimal motion Correspondingly a framework is infinitesimally rigid if it has no non trivial infinitesimal motion If a framework is flexible then there exists a non trivial infinitesimal motion Therefore if a framework is infinitesimally rigid then it is rigid However there exist rigid but not infinitesimally rigid frameworks See Figure 2 Figure 2 A rigid but not infinitesimally rigid framework The arrows show the non trivial infinitesimal motion Computing an infinitesimal motion is easy we simply solve the linear system Now we represent the linear system in a matrix form Rv 0 3 where v is a 2n dimensional velocity vector R is a m 2n matrix known as the rigidity matrix In particular each row in the rigidity matrix corresponds to an edge in G A row takes value pi pj corresponding to velocity for i pj pi corresponding to velocity for j and 0 otherwise Since we do not include the pin down equations the trivial motions global translation and rotation will yield non trivial solutions which will form a subspace of dimension 3 Therefore disregarding global translation and rotation the framework G P is infinitesimally rigid if and only if rank R 2n 3 3 2 4 Generic or Combinatorial Rigidity of a Graph So far we have explored the rigidity of a framework i e a graph along with a configuration A given graph G V E can have infinitesimally rigid rigid but infinitesimally flexible and flexible frameworks As an example refer to Figure 3 However the situation changes if we insist on generic configurations of a graph Rigidity under this constraint becomes a property of the graph as the following theorem indicates i ii iii Figure 3 i Infinitesimally rigid ii Rigid but infinitesimally flexible iii Flexible Theorem 1 If a graph has a single infinitesimally rigid framework then all its generic frameworks are rigid Thus a graph can be characterised to be either rigid or flexible in a generic sense In other words if we force a graph s configuration to be generic then rigidity becomes a property of the connectivity and not of the geometry of the formation This suggests that there must be a combinatorial way of deciding the generic rigidity of a graph without referring to any particular configuration Thus we have now two ways of looking at rigidity A framework can be either infinitesimally rigid or flexible and this property can be tested by linear algebra using the rigidity matrix A graph can be rigid or flexible if only generic configurations are considered 5 5 1 Testing Generic Rigidity of a Graph An Intuitive Approach to Testing Rigidity Informally we need to answer the following question How many distance constraints are necessary to limit a framework to only trivial motion This is equivalent to asking how many edges are necessary for a graph of n nodes to be generically rigid A priory the n nodes