This paper describes and evaluates a novel set of approaches to handle situa- tions where multiple distinct and visually differing objects are tracked, such as tracking of people and objects they are manipulating. Unlike tracking of multiple similar objects, visually different interacting objects can provide an opportunity to improve the tracking accuracy. These approaches are designed for use with Condensation/Particle Filter based algorithms, and allow drop-in replacement of tracker modules for each object type tracked. They use infor- mation about the relationships and interactions between objects to improve the tracking, rather than in order to distinguish between the objects, as in cur- rent algorithms. They are also designed to be highly efficient, for real time use. The approaches are tested on a challenging set of real data and achieve tracking performance similar to using a single very high dimensional tracker, but with vastly reduced complexity and hence much better time performance.