Computing Rigid Components of Pseudo-triangulation Mechanisms in Linear Time.
Jack Scott Snoeyink, Ileana Streinu · 2005
We investigate the problem of detecting rigid components (maximal Laman subgraphs) in a pseudotriangulation mechanism and in arbitrary pointed planar frameworks.For general Laman graphs with some missing edges, it is known that rigid components can be computed in O(n²) time.Here we make substantial use of the special geometry of pointed pseudo-triangulation mechanisms to achieve linear time. The main application is a more robust implementation and a substantial reduction in numerical computations for the solution to the Carpenter’s Rule problem given by the second author.