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.