cse590 Information Processing in Sensor Networks Lecture 3Rigidity TheoryLecturer: Jie Gao Scribe: Amitabh Basu1 Overview of the LectureIn 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 theoryare presented in this lecture. In particular, combinatorial rigidity of graphs and the pebble game for testing rigidity ofgraphs are discussed. In the following sections, we develop the theory in greater detail.2 DefinitionsA 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. Aconfiguration 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 thesame point, etc. The study of generic configurations are important because in practice, we can assume that the sensorlocations are generic.A framework G(P ) refers to a graph G along with a configuration. A particular graph can have different frame-works, with different edge lengths. A framework is called flexible if there exists a continuous deformation from thegiven configuration to another, such that edge lengths are preserved. If no such deformation exists, then it is calledrigid. See Figure 1.dabcdabc(i) (ii)dabcabcd(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 pointpi. We define the configuration space C(L) with respect to edge length constraints L = {`ij} as the collections ofconfigurations that satisfy the edge length constraints L. Thus, C(L) is a subspace of R2n.3-1Many 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 offreedom of a framework is actually the dimension of the configuration space C(L). If the configuration space has0-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 redun-dantly 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 computationalalgebraic geometry or topology. However, the tangent space of C(L) is relatively more tractable. The next sectionillustrates the important results regarding the tangent space.3 Infinitesimal Motion and Infinitesimal RigidityInfinitesimal rigidity is defined over the tangent space. In particular, the configuration space of a framework is repre-sented byC = {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. Weusually factor out the global rigid motion (translation and rotation) by pinning down an edge. So we include the “pindown” 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-trivialsolution, the infinitesimal motion is called non-trivial. A framework is infinitesimally flexible if it has a non-trivialinfinitesimal motion. Correspondingly, a framework is infinitesimally rigid if it has no non-trivial infinitesimal mo-tion. If a framework is flexible, then there exists a non-trivial infinitesimal motion. Therefore, if a framework isinfinitesimally 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 linearsystem 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, eachrow in the rigidity matrix corresponds to an edge in G. A row takes value pi− pjcorresponding to velocity for i,pj− picorresponding to velocity for j, and 0 otherwise. Since we do not include the “pin down” equations, the trivialmotions (global translation and rotation) will yield non-trivial solutions which will form a subspace of dimension3. Therefore, disregarding global translation and rotation, the framework G(P ) is infinitesimally rigid if and only ifrank(R) = 2n − 3.3-24 Generic or Combinatorial Rigidity of a GraphSo 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 toFigure 3. However, the situation changes if we insist on generic configurations of a graph. Rigidity under thisconstraint 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) FlexibleTheorem 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 agraph’s configuration to be generic then rigidity becomes a property of the connectivity and not of the geometry of theformation. This suggests that there must be a combinatorial way of deciding the generic rigidity of a graph, withoutreferring to any particular configuration.Thus we have now two ways of looking at rigidity. A framework can be either infinitesimally rigid or flexible andthis property can be tested by linear algebra using the rigidity matrix. A graph can be rigid or flexible, if only genericconfigurations are considered.5 Testing Generic Rigidity of a Graph5.1 An Intuitive Approach to Testing