| Dynamic Maintenance (2007) | |||||||||||||||||
Abstract | |||||||||||||||||
| We consider the following dynamic data structure problem. Given a collection of rigid bodies moving in 3-dimensional space and hinged together in a kinematic structure, our goal is to efficiently maintain a data structure that allows us to quickly answer range queries as the bodies move. This kinematic data structure problem arises in a variety of applications such as conformational search in molecular biology, simulation of hyper-redundant robots, collision detection, and computer animation. We study several models for dynamic maintenance of such structures and devise algorithms under these models. We obtain tight results on the worst-case, amortized, and randomized complexity of the data structure problem. For the offline version of the problem, we establish NP-hardness and provide efficient approximation algorithms. Key words. data structure, approximation algorithm, kinematics, range queries, conformational search, molecular biology, robotics, collision detection, computer animatio... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||