Computational Geometry & Rigidity Theory

My research interests currently fall under the umbrella area of "computational geometry," the study of algorithmic and fundamental problems with geometric content. More specifically, I work in the area of "rigidity theory," focusing on understanding the structural properties of a broadly defined set of objects called "geometric constraint systems." The versatility of these systems to model domains ranging from proteins to sensor networks to mechanical engineering designs results in a wide spectrum of applications and interdisciplinary projects. In particular, I am currently working on projects that address questions on protein flexibility, sensor network localization and computer aided design (CAD). My projects generally have two lines of research: theoretical and applied. This allows flexibility in involving undergraduate students from a variety of backgrounds and interests.

A geometric constraint system is made up of geometric entities upon which constraints are placed. The most basic structure, called a "bar-and-joint" structure, is composed of points with fixed-length distances between specified pairs; the points can be viewed as universal joints with bars between them representing the distance constraints. The fundamental question for the rigidity theory is whether a given bar-and-joint structure is "rigid" (does not allow internal motions) or "flexible" (allows a continuous deformation while respecting the distance constraints). For instance, a triangle in the plane is rigid (intuitively, it cannot take on any other shape without changing an edge distance), whereas a square is flexible (it may continuously flex from a square to a rhombus to a flattened form while maintaining the edge distances). However, even this simple question can be a difficult research problem. For the planar case of bar-and-joint structures, the answer is surprisingly elegant, characterized by a simple combinatorial counting property. In sharp contrast, the case for 3D bar-and-joint structures is a conspicuously open question and is arguably the most challenging in the rigidity theory community today.

Theoretical results may immediately lead to significant advances in the applied domains. For instance, the 3D bar-and-joint structures previously mentioned can model a protein or a structural design made by a mechanical engineer in CAD software. Algorithms developed in the theory would directly apply as methods for analyzing protein flexibility or giving feedback to a CAD user. The 3D structure of a protein is generally understood to dictate its function. Furthermore, proteins flex near their native conformation, and it is now believed that this flexibility is an important part of protein docking or binding events. Computational tools that can aid biochemists in a deeper understanding of a protein's flexibility may be the key to more effective and efficient drug design. CAD software allows mechanical engineers to design anything from a pair of pliers to an airplane. Most CAD software is designed to allow users to create systems using geometric constraints, defining precisely a geometric constraint system. The systems created by CAD users are quite intricate, so it is necessary to provide useful feedback to help the users achieve their design goals. However, this is an extremely hard problem, requiring the detection and analysis of dependencies in complicated algebraic systems. Rigidity theory strives for achieving combinatorial characterizations; results of this flavor can lead to simple and elegant solutions for providing real-time feedback.