Problems in Generic Combinatorial Rigidity: Genericity, Enumeration and Emergence of Components

05 Dec
Friday, 12/05/2008 11:30am
Ph.D. Dissertation Proposal Defense

Louis Theran

Computer Science Building, Room 151

A fundamental problem in discrete and computational geometry asks for the reconstruction of a set of n unknown points in the plane, given a set of m pairwise distances between them. The related planar rigidity problem asks when the space of allowed reconstructions is discrete, modulo rigid motions of the plane. More intuitively, the rigidity problem asks when a planar structure made of fixed-length bars connected by universal joints (a bar-joint framework) allows only the trivial rigid body motions. The bar-and-joint rigidity model has been very well studied theoretically, and widely applied in engineering, architecture, CAD, biology, and sensor networks. While both the reconstruction problem and the rigidity problem appear to be intractable in the most general case, the celebrated Maxwell-Laman Theorem shows that for generic (almost all choices of distances), the rigidity problem can be answered by a combinatorial condition: whether the framework's graph meets certain hereditary counts. Moreover, the counting condition can be checked efficiently.

In recent work we have explored the combinatorial and algorithmic theory of (k,l)-sparse graphs and hypergraphs, which generalize the hereditary ``degree of freedom'' counts arising in the Maxwell-Laman Theorem. We described new algorithms for decomposing graphs into edge-disjoint spanning trees, new decomposition characterizations of sparse graphs, the first general algorithms for recognizing sparse hypergraphs, and a new linear representation theorem for sparse graphs and hypergraphs. We also introduced a new model of slider-pinning rigidity, which generalizes the rigidity problem to the setting where some of the points are constrained to move on fixed tracks, rigidity attached to the plane. We developed the algebraic, linear, and combinatorial rigidity theories in the slider-pinning model, proving the analogue of the Maxwell-Laman theorem for slider-pinning. As a corollary, we obtained a new, combinatorial proof of the Maxwell-Laman theorem, and a new, combinatorial approach to genericity that is amenable to algorithmic analysis.

In this thesis we plan to continue our work in combinatorial rigidity. Motivated by an important open problem in sold-state physics, we consider the emergence of large (generically) rigid components in Erdos-Renyi random graphs that have linearly many edges; recently we have established that the rigid components are either very large or constant sized. We also plan to address the problem of efficiently enumerating the subset of minimally pinned bar-and-slider structures that correspond to the information available from sparse sensor networks with a few GPS measurements. We will also describe a geometric problem relating to lowest-degree interpolating polynomials that we have recently worked on.

Proposal Dissertation Defense Required for Ph.D.
Advisor: Ileana Streinu