Finding and Maintaining Rigid Components.
Audrey W. Q. Lee, Ileana Streinu, Louis Theran · 2005
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 pairfind, 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.