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 $n$ 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 $v$, it is known that $v=f(t)$. Kinetic data structures allow queries on a system at the current virtual time $t$, and two additional operations:

• ${\textrm {advance}}(t)$: Advances the system to time $t$.
• ${\textrm {change}}(v,f(t))$: Alters the trajectory of value $v$ to $f(t)$, as of the current time.

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:

1. Store a data structure on the system at the current time $t$. This data structure allows queries on the system at the current virtual time.
2. Augment the data structure with certificates. Certificates are conditions under which the data structure is accurate. The certificates are all true now, and the data structure will only cease to be accurate when one of the certificates is no longer true.
3. Compute the failure time of each certificate, the time when it will cease to be true.
4. Store the certificates in a priority queue, keyed by their failure times
5. To advance to time $t$, look at the certificate with the lowest failure time from the priority queue. If the certificate fails before time $t$, pop it from the queue and fix the data structure so it is accurate at the time of failure, and update the certificates. Repeat this until the certificate with the lowest failure time in the priority queue fails after time $t$. If the certificate with the lowest failure time in the priority queue fails after time $t$, then all certificates are true at time $t$ so the data structure can correctly answer queries at time $t$.

The approach can be summarized in pseudocode as follows. The data structure D is valid at the current time now and is augmented with a priority queue Q of certificates keyed by failure time:

function advance(t):
    while Q is not empty and minFailureTime(Q) ≤ t:
        c := extractMin(Q)              (the failing certificate)
        now := failureTime(c)
        repair D so it is accurate at time now
        remove invalidated certificates from Q
        compute failure times of the new certificates
        insert the new certificates into Q
    now := t                            (all certificates now hold at t)

function change(v, f):            (trajectory change, as of time now)
    for each certificate c in Q involving v:
        recompute failureTime(c) and update its key in Q

The number of certificates involving any one value, which bounds the work performed by change, is the locality of the structure.

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 $n$, or is $O(n^{\epsilon })$ for arbitrarily small $\epsilon$, where $n$ 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 $O(n\operatorname {polylog} n)$ or $O(n^{1+\epsilon })$ for arbitrarily small $\epsilon$. (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 $t=\infty$ 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 $t=\infty$. A kinetic data structure is said to be efficient if this ratio is small.

Discrete-time operation

The certificates approach assumes events are processed one at a time, in order, at their exact real-valued failure times. Many systems that track moving objects, such as physical simulations and game servers, instead observe the world at fixed time steps. Between observations, several certificates may fail, so the data structure must repair a batch of failures at each step rather than a single failure at an exact time. Guibas identifies recovery after multiple certificate failures as a structural open problem for the framework.

A related subtlety is that a certificate set can constitute a historical proof: it certifies the attribute only in combination with the fact that no certificate failed earlier in the motion. If the system can change between observations, an absolute proof, a certificate set that validates the attribute in any state of the world, may be required instead.

When trajectories are known and failure times are quantized to integer time steps, the priority queue of certificates can be replaced by a bucket queue indexed by step number, reducing event scheduling and extraction to constant time per operation.

In practice

Implementations of kinetic data structures must compute certificate failure times by finding roots of polynomials, which raises numerical robustness issues absent from the theoretical model, where exact constant-time root finding is assumed. Russel studied exact and filtered approaches to event scheduling and the practical costs of maintaining the event queue in implementations of kinetic Delaunay triangulations and related structures.

Kinetic approaches to collision detection can bound the number of events by the relative separation of the objects rather than by a fixed sampling rate, avoiding both oversampling and undersampling. In interactive applications such as games and physics engines, the widely used sweep and prune broad-phase algorithm maintains sorted orders of bounding-box extrema and repairs them incrementally as objects move, and can be viewed as a kinetic data structure whose certificates are the adjacencies in the sorted orders.

A practical obstacle to wider adoption is the cost of trajectory changes: every certificate involving an object must be re-evaluated when that object's motion changes, which the locality measure is designed to bound. Hierarchical motion descriptions, in which nearby objects share motion components, have been proposed to reduce this cost.

Open problems

Guibas's survey lists several problems that remain open, including finding an efficient, responsive, local, and compact kinetic data structure for the convex hull of points moving in dimension three or higher; tightening the gap between the quadratic lower bound and near-cubic upper bound on the number of kinetic Voronoi diagram events; maintaining a kinetic Euclidean minimum spanning tree with a subquadratic number of events; and developing motion-sensitive analyses whose costs are parameterized by the coherence of the motion rather than by the worst case. Structural questions include recovery after multiple certificate failures and the analysis of non-canonical, history-dependent structures, for which mathematical techniques are lacking.

Rahmati improved the event bound for the kinetic Euclidean minimum spanning tree in the plane from $O(n^{4})$ to roughly $O(n^{3}\log n)$ up to Davenport–Schinzel factors, and posed successor problems including a kinetic Euclidean minimum spanning tree with a sub-cubic number of events and worst-case rather than amortized responsiveness for kinetic nearest-neighbor structures.

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:

• Affine:(Linear functions) $f(t)=at+b$
• Bounded-degree algebraic:(Polynomial functions of bounded degree) $f(t)=\sum _{i=0}^{n}a_{i}t^{i}$ for some fixed $n$.
• Pseudo-algebraic: Trajectories such that any certificate of interest flips between true and false $O(1)$ times.

Examples

• Kinetic tournament
• Kinetic sorted list
• Kinetic heap
• Kinetic convex hull
• Kinetic closest pair
• Kinetic minimum spanning tree
• Kinetic Euclidean minimum spanning tree
• Kinetic Yao graph
• Kinetic Semi-Yao graph (a variant of the theta graph)
• Kinetic all nearest neighbors
• Kinetic all k-nearest neighbors