Kinetic data structure
A kinetic data structure is a data structure used to track an attribute of a geometric system that is moving continuously. For example, a kinetic convex hull data structure maintains the convex hull of a group of formula_1 moving points. The development of kinetic data structures was motivated by computational geometry problems involving physical objects in continuous motion, such as collision or visibility detection in robotics, animation or computer graphics. Overview. Kinetic data structures are used on systems where there is a set of values that are changing as a function of time, in a known fashion . So the system has some values, and for each value formula_2, it is known that formula_3. Kinetic data structures allow queries on a system at the current virtual time formula_4, and two additional operations: Additional operations may be supported. For example, kinetic data structures are often used with a set of points. In this case, the structure typically allows points to be inserted and deleted. Contrast with traditional data structures. A kinetic data structure allows the values stored in it to change continuously with time. In principle, this can be approximated by sampling the position of the points at fixed  intervals of time, and deleting and re-inserting each point into a "static" (traditional) data structure. However, such an approach is vulnerable to oversampling or undersampling, depending on what interval of time is used, and can also be wasteful of computational resources. Certificates approach. The following general approach can be used to construct kinetic data structures: Types of events. Certificate failures are referred to as "events". An event is considered internal if the property maintained by the kinetic data structure does not change when the event occurs. An event is considered external if the property maintained by the data structure  changes when the event occurs. Performance. When using the certificates approach, there are four measures of performance. We say a quantity is small if it is a polylogarithmic function of formula_1, or is formula_18 for arbitrarily small formula_19, where formula_1 is the number of objects: Responsiveness. Responsiveness is the worst case amount of time required to fix the data structure and augmenting certificates when a certificate fails. A kinetic data structure is responsive if the worst case amount of time required for an update is small. Locality. The maximum number of certificates any one value is involved in. For structures  involving moving points, this is that maximum number of certificates any one point is involved in. A kinetic data structure is local if the maximum number of certificates any one value is involved with is small. Compactness. The maximum number of certificates used to augment the data structure at any time. A kinetic data structure is compact if the number of certificates it uses is formula_21 or formula_22 for arbitrarily small formula_19. (a small factor more than linear space) Efficiency. The ratio of the worst case number of events that can occur when the structure is advanced to formula_24 to  the worst case number of "necessary changes" to the data structure. The definition of "necessary changes" is problem dependent. For example, in the case of a kinetic data structure maintaining the kinetic hull of a set of moving points, the number of necessary changes would be the number of times the kinetic hull changes as time is advanced to formula_24. A kinetic data structure is said to be efficient if this ratio is small. Types of Trajectories. The performance of a certain kinetic data structure may be analyzed for certain types of trajectories. Typically, the following types of trajectories are  considered: