# Finding and maintaining rigid components

 Authors: Audrey Lee, Ileana Streinu, and Louis Theran Proc. of: Canadian Conference on Computational Geometry CCCG’05, 2005. Full text: URL

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.