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.
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.
Kinetic data structures allow queries on a system at the current virtual time
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.
The following general approach can be used to construct kinetic data structures:[5] Certificate failures are referred to as "events".
is the number of objects: 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.
A kinetic data structure is local if the maximum number of certificates any one value is involved with is small.
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
(a small factor more than linear space) The ratio of the worst case number of events that can occur when the structure is advanced to
The performance of a certain kinetic data structure may be analyzed for certain types of trajectories.