Given a database of moving objects, interpenetration between any objects must
be detected. The simplest approach is to check each object against every other
object in a pairwise fashion. This is of the order 
for n
objects and for a large database of objects is too inefficient. One method of
decreasing the time spent searching for collisions is to reduce the number of
object comparisons.
A simple method employed by Garcia-Alonso [GASF94] was what they called the collision interest matrix. This is simply a matrix containing flags which indicate whether collision detection has to be carried out between any given pair of objects. The collision interest matrix allows tests between objects to be ignored if it is impossible for the objects in question to collide (for example if relative motion cannot occur between them). Another case where collision detection can be ignored is when two objects come into contact for a period of time. For the time period the objects can be flagged so that no collision detection is carried out between them, and then the collision detection can be resumed once they are no longer in contact. During this period of contact, it is up to the dynamics or controlling part of the simulator to ensure the objects do not interpenetrate, and to decide when the objects are no longer considered to be in contact.
Linked bodies are another example where there is contact between objects. Parts of the objects are in constant contact so interpenetration testing can be ignored (again the dynamics/driving module of the simulation is responsible for keeping these objects in an allowable state).
Using a collision interest matrix can reduce the number of interpenetration tests that need to be carried out, however there may still be a large number of objects that need to be tested against each other for interpenetration. Two techniques that can be used to reduce the number of tests are spatial subdivision (or spatial coherence) [WW92, pp241--248,][FKN80,FTI86,PM91,HT92] and bounding volumes [WW92, pp234--238,][GS87]. These techniques have been used and studied extensively in the field of ray tracing. In ray tracing, ray-object intersection testing consumes the greatest amount of time, so dramatic speed increases can be obtained by reducing the number of objects each ray is tested against, and/or by reducing the cost of each test.