@INPROCEEDINGS {components,
title = {Finding and Maintaining Rigid Components},
author = {Lee, Audrey and Streinu, Ileana and Theran, Louis},
booktitle = {Proceedings of the Canadian Conference of Computational Geometry},
year = {2005},
address = {Windsor, Ontario},
note = {\url{http://cccg.cs.uwindsor.ca/papers/72.pdf}},
abstract = {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(n2 ). To this end, we intro- 
duce 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.},
}