A kinetic data structure is a data structure used to track an attribute of a geometric system that is moving continuously. [1] [2] [3] [4] For example, a kinetic convex hull data structure maintains the convex hull of a group of 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.
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 , it is known that . Kinetic data structures allow queries on a system at the current virtual time , 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.
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". 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.
When using the certificates approach, there are four measures of performance. We say a quantity is small if it is a polylogarithmic function of , or is for arbitrarily small , where 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.
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.
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 or for arbitrarily small . (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 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 . A kinetic data structure is said to be efficient if this ratio is small.
The performance of a certain kinetic data structure may be analyzed for certain types of trajectories. Typically, the following types of trajectories are considered:
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.
Orbital mechanics or astrodynamics is the application of ballistics and celestial mechanics to the practical problems concerning the motion of rockets and other spacecraft. The motion of these objects is usually calculated from Newton's laws of motion and the law of universal gravitation. Orbital mechanics is a core discipline within space-mission design and control.
In mathematical analysis, a family of functions is equicontinuous if all the functions are continuous and they have equal variation over a given neighbourhood, in a precise sense described herein. In particular, the concept applies to countable families, and thus sequences of functions.
In mathematics, the Shapiro inequality is an inequality proposed by Harold S. Shapiro in 1954.
In computer science, fractional cascading is a technique to speed up a sequence of binary searches for the same value in a sequence of related data structures. The first binary search in the sequence takes a logarithmic amount of time, as is standard for binary searches, but successive searches in the sequence are faster. The original version of fractional cascading, introduced in two papers by Chazelle and Guibas in 1986, combined the idea of cascading, originating in range searching data structures of Lueker (1978) and Willard (1978), with the idea of fractional sampling, which originated in Chazelle (1983). Later authors introduced more complex forms of fractional cascading that allow the data structure to be maintained as the data changes by a sequence of discrete insertion and deletion events.
The dynamic convex hull problem is a class of dynamic problems in computational geometry. The problem consists in the maintenance, i.e., keeping track, of the convex hull for input data undergoing a sequence of discrete changes, i.e., when input data elements may be inserted, deleted, or modified. It should be distinguished from the kinetic convex hull, which studies similar problems for continuously moving points. Dynamic convex hull problems may be distinguished by the types of the input data and the allowed types of modification of the input data.
A Kinetic Heap is a kinetic data structure, obtained by the kinetization of a heap. It is designed to store elements where the priority is changing as a continuous function of time. As a type of kinetic priority queue, it maintains the maximum priority element stored in it. The kinetic heap data structure works by storing the elements as a tree that satisfies the following heap property – if B is a child node of A, then the priority of the element in A must be higher than the priority of the element in B. This heap property is enforced using certificates along every edge so, like other kinetic data structures, a kinetic heap also contains a priority queue to maintain certificate failure times.
A kinetic convex hull data structure is a kinetic data structure that maintains the convex hull of a set of continuously moving points. It should be distinguished from dynamic convex hull data structures, which handle points undergoing discrete changes such as insertions or deletions of points rather than continuous motion.
A kinetic closest pair data structure is a kinetic data structure that maintains the closest pair of points, given a set P of n points that are moving continuously with time in a metric space. While many efficient algorithms were known in the static case, they proved hard to kinetize, so new static algorithms were developed to solve this problem.
A Kinetic Tournament is a kinetic data structure that functions as a priority queue for elements whose priorities change as a continuous function of time. It is implemented analogously to a "tournament" between elements to determine the "winner", with the certificates enforcing the winner of each "match" in the tournament. It supports the usual priority queue operations - insert, delete and find-max. They are often used as components of other kinetic data structures, such as kinetic closest pair.
A kinetic sorted list is a kinetic data structure for maintaining a list of points under motion in sorted order. It is used as a kinetic predecessor data structure, and as a component in more complex kinetic data structures such as kinetic closest pair.
A kinetic diameter data structure is a kinetic data structure which maintains the diameter of a set of moving points. The diameter of a set of moving points is the maximum distance between any pair of points in the set. In the two dimensional case, the kinetic data structure for kinetic convex hull can be used to construct a kinetic data structure for the diameter of a moving point set that is responsive, compact and efficient.
A kinetic triangulation data structure is a kinetic data structure that maintains a triangulation of a set of moving points. Maintaining a kinetic triangulation is important for applications that involve motion planning, such as video games, virtual reality, dynamic simulations and robotics.
A Kinetic Heater is a kinetic priority queue similar to a kinetic heap, that makes use of randomization to simplify its analysis in a way similar to a treap. Specifically, each element has a random key associated with it in addition to its priority. The kinetic heater is then simultaneously a binary search tree on the element keys, and a heap on the element priorities. The kinetic heater achieves (expected) asymptotic performance bounds equal to the best kinetic priority queues. In practice however, it is less efficient since the extra random keys need to be stored, and the procedure to handle certificate failure is a rotation instead of a simple swap.
A Kinetic hanger is a randomized version of a kinetic heap whose performance is easy to analyze tightly. A kinetic hanger satisfies the heap property but relaxes the requirement that the tree structure must be strictly balanced, thus insertions and deletions can be randomized. As a result, the structure of the kinetic hanger has the property that it is drawn uniformly at random from the space of all possible heap-like structures on its elements.
A Kinetic Priority Queue is an abstract kinetic data structure. It is a variant of a priority queue designed to maintain the maximum priority element when the priority of every element is changing as a continuous function of time. Kinetic priority queues have been used as components of several kinetic data structures, as well as to solve some important non-kinetic problems such as the k-set problem and the connected red blue segments intersection problem.
A kinetic width data structure is a kinetic data structure which maintains the width of a set of moving points. In 2D, the width of a point set is the minimum distance between two parallel lines that contain the point set in the strip between them. For the two dimensional case, the kinetic data structure for kinetic convex hull can be used to construct a kinetic data structure for the width of a point set that is responsive, compact and efficient.
A kinetic smallest enclosing disk data structure is a kinetic data structure that maintains the smallest enclosing disk of a set of moving points.
Kinetic minimum box is a kinetic data structure to maintain the minimum bounding box of a set of points whose positions change continuously with time. For points moving in a plane, the kinetic convex hull data structure can be used as a basis for a responsive, compact and efficient kinetic minimum box data structure.
In computational geometry, the convex layers of a set of points in the Euclidean plane are a sequence of nested convex polygons having the points as their vertices. The outermost one is the convex hull of the points and the rest are formed in the same way recursively. The innermost layer may be degenerate, consisting only of one or two points. The problem of constructing convex layers has also been called onion peeling or onion decomposition.
