| Abstract Analyzing Rigidity with Pebble Games (2008) | |||||||||||||||
Abstract | |||||||||||||||
| For a set of points, how many pair-wise distances must be prescribed to determine a discrete set of embeddings? This question, and related generalizations, is the central one in combinatorial rigidity, where we seek an answer via an efficiently testable property of graphs. We present a poster summarizing results on algorithms for a variety of rigidity-related problems, including some of our very recent work. The accompanying demo emphasizes the relevant rigidity cases using our comprehensive software implementation of the pebble game paradigm. 1 Rigidity Models We start with a brief overview of the models of rigidity relevant for the presented work. For each model, we describe the geometric constraints that define it and the rigidity property we want to determine. Planar bar-and-joint rigidity. A bar-and-joint framework consists of universal joints in the plane connected by fixed-length bars. If the only motions maintaining the lengths of all the bars are trivial rigid motions (translations and rotations), the framework is rigid (see Figure 1(a)); otherwise, it is flexible (see Figure | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||