Report Number: CS-TN-95-23
Institution: Stanford University, Department of Computer Science
Title: Dynamic Maintenance of Kinematic Structures
Author: Halperin, Dan
Author: Latombe, Jean-Claude
Author: Motwani, Rajeev
Date: August 1995
Abstract: We study the following dynamic data structure problem. Given a collection of rigid bodies moving in three-dimensional space and hinged together in a kinematic structure, our goal is to maintain a data structure that describes certain geometric features of these bodies, and efficiently update it as the bodies move. This data structure problem seems to be fundamental and it comes up in a variety of applications such as conformational search in molecular biology, simulation of hyper-redundant robots, collision detection and computer animation. In this note we present preliminary results on a few variants of the problem.