BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-00-1629
       ENTRY:: July 26, 2000
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: KINETIC VERTICAL DECOMPOSITION TREES
        TYPE:: Thesis
        TYPE:: Technical Report
      AUTHOR:: COMBA, JOAO LUIZ DIHL
        DATE:: March 2000
       PAGES:: 141
    ABSTRACT:: 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.
       NOTES:: [Adminitrivia V1/Prg/20000726]
         END:: STAN//CS-TR-00-1629