Geometric Constraints and Configurations

Selected publications / opensource software

A recent PhD graduate Jialong Cheng from the Sitharam group has made progress on a 150 year open problem posed by James Clerk Maxwell in 1874 concerning a characterization of when a 3D bar-linkage (in effect a distance constraint system) is rigid. The goal is a characterization that is purely combinatorial, i.e., independent of the actual lengths of the bars in the linkage (distance values in the constraint system), yielding a graph algorithm for determining 3D rigidity. The question was completely answered for 2D in 1970 and has since given rise to an entire area of Mathematics called Combinatorial rigidity theory. Jialong shows that either he has found a much sought-after combinatorial characterization of rigidity of 3D distance constraint systems, or he has disproven another longstanding conjecture about a purely combinatorial abstract rigidity notion.
Two of the group's previous results led up to the above result: one of them settled another longstanding question that has remained open since Maxwell. Both earlier results were well-received in two of three invited talks (links: talk1 and talk2) the group gave at a Fields institute workshop in October 2011. One of these papers gives systematic constructions of so-called "nucleation-free" graphs that are highly flexible and yet counter-intuively have pairs of vertices that maintain a fixed distance (implied non-edges). This is an obstacle in obtaining combinatorial characterizations of 3D rigidity. An earlier version appeared as a conference paper with Ileana Streinu of UMass in the Canadian Conference in Computational Geometry in 2009.
The last of the 3 invited talks the Sitharam group gave at Fields Institute Workshop in October 2011 concerned fundamental mathematical results concerning when so-called Cayley configuration spaces of distance constraint systems (linkages) in 2D have low complexity, i.e., the boundaries of these spaces can be described using simple ruler and compass construction. Such algebraic questions date back to the time of Galois. This work is a continuation of recent papers by a former PhD student from the group, Heping Gao and recently graduated masters student Ugandhar on efficient parametrizations of Cayley configuration spaces