|
Traditional collision detection techniques based on distance computations or bounding volume hierarchies do not work well for highly deformable objects such as folding molecules: there are too many possible near contacts and a hierarchy needs continuous major updates. We have been developing techniques based on the notion of graph spanners that provide a lightweight combinatorial alternative solution to the problem of contact detection among deforming molecules. A spanner for a molecule is a simple data structure that consists of a list of element pairs providing a set of "shortcuts" in going from one part of the molecule to another. The spanner guarantees that the shortest path between any two elements in the graph defined by the natural atom connectivity and these additional shortcuts is a close approximation to the Euclidean distance between the atoms. In particular, before two atoms can collide, there has to be a spanner shortcut between them. During the fourth year of the grant we have further enhanced the data structures that support spanners.