Minimal and Redundant Bearing Rigidity: Conditions and Applications

Abstract

This article studies the notions of minimal and 1-redundant bearing rigidity. A necessary and sufficient condition for the numbers of edges in a graph of n (n >= 3) vertices to be minimally bearing rigid (MBR) in R-d (d >= 2) is proposed. If 3 <= n <= d + 1, a graph is MBR if and only if it is the cycle graph. In case n > d + 1, a generically bearing rigid graph is minimal if it has precisely 1 + [n - 2/d-1] x d + mod(n - 2, d - 1) + sgn(mod( n - 2, d - 1)) edges. Then, several conditions for 1-redundant bearing rigidity are derived. Based on the mathematical conditions, some algorithms for generating generically, minimally, and 1-redundantly bearing rigid graphs are given. Furthermore, two applications of the new notions to optimal network design and formation merging are also reported.