60RIGIDITYANDSCENEANALYSIS.PDFVIP

60 RIGIDITY AND SCENE ANALYSIS Walter Whiteley INTRODUCTION Rigidity and flexibility of frameworks (motions preserving lengths of bars) and scene analysis (liftings from plane polyhedral pictures to spatial polyhedra) are two core examples of a general class of geometric problems: (a) Given a discrete configuration of points ,lines ,planes . . . in Euclidean space and a set of geometric constraints (fixed lengths for rigidity ,fixed incidences and fixed projections of points for scene analysis) ,what is the set of solutions and what is its local form: discrete? k-dimensional? (b) Given a structure satisfying the constraints ,is it unique ,or at least locally unique ,up to trivial changes ,such as congruences for rigidity ,or vertical scale for liftings? (c) How does this answer depend on the combinatorics of the structure and how does it depend on the specific geometry of the initial data or object? The rigidity of frameworks examines points constrained by fixed distances be- tween pairs ,using vocabulary and linear techniques drawn from structural engineer- ing: bars and joints ,first-order rigidity and first-order flexes ,and static rigidity and static self-stresses (Section 60.1). Scene analysis and the dual concept of parallel drawings are described in Section 60.2. Finally ,reciprocal diagrams form a funda- mental geometric connection between liftings of polyhedral pictures and self-stresses in frameworks (Section 60.3). These core problems have a wide range of applications across many areas of applied geometry. The methods used and the results obtained for these problems serve as a model for what might be hoped for other sets of constraints (plane first-