|
Kinetic Diameter (data)
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. 2D Case The pair of points with maximum pairwise distance must be one of the pairs of antipodal points of the convex hull of all of the points. Note that two points are antipodal points if they have parallel supporting lines. In the static case, the diameter of a point set can be found by computing the convex hull of the point set, finding all pairs of antipodal points, and then finding the maximum distance between these pairs. This algorithm can be kinetized as follows: Consider the dual of the point set. The points dualize to lines and the convex hull ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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(t): Advances the system to time t. *\textrm(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 struct ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |