Dynam ic M aintenance of Kinematic Structures

摘要

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.