Swarthmore College Department of Computer Science

Talk by Audrey Lee, UMass Amherst

Geometric Constraint Systems and Pebble Game Algorithms
Thursday, February 7, 2008
4:00 pm in Science Center 240
Reception and refreshments at 3:45 pm

Abstract

Bar-and-joint structures, made up of rigid bars connected by universal joints, arise in important current applications; in engineering, they can model robots or buildings and, in biology, they can model proteins. Although such structures are the simplest type in a wide range of constraint structures, their mechanical properties (rigidity and flexibility) are still not fully understood.

For certain types of constraint systems, combinatorial results have led to an elegant and efficient algorithm called the pebble game. In this talk, I will present this algorithm and several generalizations and applications, using Java applets and physical models for demonstration. In addition, I will describe current work that addresses constraint systems arising from the widely-used CAD (Computer Aided Design) application SolidWorks.