Kinetic vertical decomposition trees
Leonidas Guibas, João L. D. Comba · 1999
This thesis presents a new structure called the Kinetic Vertical Decomposition Tree (KVD), used for the dynamic maintenance of visibility information for a set of moving objects in space. The KVD is a single structure that not only (1) allows dynamic maintenance of visibility, but also (2) represents a vertical decomposition of the space, (3) allows collision detection among moving objects, and (4) it is kinetically maintained based on the kinetic data structures framework. The KVD is a special type of Binary Space Partition tree (BSP), a hierarchical data structure commonly used in solid modeling and computer graphics for feature classification and visibility determination. In the KVD, additional cuts are introduced from edges and vertices, so that a vertical decomposition is formed. The bounded complexity of the cells in this decomposition allows the creation of certificates that indicate times when the movement of objects causes a change in the decomposition. These certificates are used within the framework of kinetic data structures to identify when the structure of the KVD changes. The update of the KVD involves local changes in the tree, accomplished by special update algorithms.