Rigidity and Pebble games

Audrey Lee, Ileana Streinu, Louis Theran

Overview

How many pair-wise distances must be prescribed between an unknown set of points, and how should they be distributed, to determine only a discrete set of possible solutions? These questions, and related generalizations, are central in a variety of applications ranging from engineering to protein structure determination to origami folding. Combinatorial rigidity answers questions on generic structures via graph properties.

This web site is devoted to demonstrations of our interactive software for Pebble Game Algorithms for analyzing the rigidity and flexibility of a variety of structures.

Contents

Rigidity Models and Questions.

Definitions and concepts of rigidity, flexibility, and rigid components in the context of several models of mechanical frameworks.

Rigid body-bar framework

Pebble Games for Rigidity.

Demos of the Pebble Game paradigm applied to several fundamental rigidity questions.

The pebble game for rigid components

Pebble Games for Sparse Graphs.

Generalizations of sparsity and pebble games.

The pebble game with colors

Bibliography.

Links to our relevant papers.

Discrete Math., 308(8), 2008.

Research funded by the NSF under grants NSF CCF-0430990 and NSF-DARPA CARGO CCR-0310661.