Finding and maintaining rigid components

We give the first complete analysis that the complexity of finding and maintaining rigid components of planar bar-and-joint frameworks and arbitrary \(d\)-dimensional body-and-bar frameworks, using a family of algorithms called pebble games, is \(O(n^2)\). To this end, we introduce a new data structure problem called union pair-find, which maintains disjoint edge sets and supports pair-find queries of whether two vertices are spanned by a set.

We present solutions that apply to generalizations of the pebble game algorithms, beyond the original rigidity motivation.