|
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 stru ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Data Structure
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data, i.e., it is an algebraic structure about data. Usage Data structures serve as the basis for abstract data types (ADT). The ADT defines the logical form of the data type. The data structure implements the physical form of the data type. Different types of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, relational databases commonly use B-tree indexes for data retrieval, while compiler implementations usually use hash tables to look up identifiers. Data structures provide a means to manage large amounts of data efficiently for uses such as large databases and internet indexing services. Usually, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kinetic Convex Hull
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. The 2D case The best known data structure for the 2-dimensional kinetic convex hull problem is by Basch, Guibas, and Hershberger. This data structure is responsive, efficient, compact and local. The data structure The dual of a convex hull of a set of points is the upper and lower envelopes of the dual set of lines. Therefore, maintaining the upper and lower envelopes of a set of moving lines is equivalent to maintaining the convex hull of a set of moving points. Computing upper and lower envelopes are equivalent problems, so computing the upper envelope of a set of lines is equivalent to computing the convex hull of a set of moving points. The upper envelo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computational Geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity. Analysis of algorithms, Computational complexity is central to computational geometry, with great practical significance if algorithms are used on very large datasets containing tens or hundreds of millions of points. For such sets, the difference between O(''n''2) and O(''n'' log ''n'') may be the difference between days and seconds of computation. The main impetus for the development of computational geometry as a discipline was progress in computer graphics and computer-aided design and manufacturing (Computer-aided design, CAD/Compu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polylogarithmic Function
In mathematics, a polylogarithmic function in is a polynomial in the logarithm of , : a_k (\log n)^k + a_ (\log n)^ + \cdots + a_1(\log n) + a_0. The notation is often used as a shorthand for , analogous to for . In computer science, polylogarithmic functions occur as the order of time or memory used by some algorithms (e.g., "it has polylogarithmic order"). All polylogarithmic functions of are for every exponent (for the meaning of this symbol, see small o notation), that is, a polylogarithmic function grows more slowly than any positive exponent. This observation is the basis for the soft O notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ... . References * Mathematical analysis Polynomials Analysis of algorithms {{comp-sci-theory-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kinetic Tournament
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" (maximum or minimum element), with the Kinetic data structure#Certificates Approach, 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. Implementation A kinetic tournament is organized in a binary tree-like structure, where the leaves contain the elements, and each internal node contains the larger (or smaller) of the elements in its child nodes. Thus, the Tree (data structure), root of the tree contains the maximum (or minimum) element at a given time. The validity of the structure is enforced by creating a certificate at each node ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kinetic Sorted List
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. Implementation This data structure maintains a list of the elements in sorted order, with the certificates enforcing the order between adjacent elements. When a certificate fails, the concerned elements are swapped. Then at most three certificates must be updated, the certificate of the swapped pair, and the two certificates involving the swapped elements and the elements of the sorted list which directly precede and follow the swapped pair. For example, given a sorted list , the certificates will be [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kinetic Heap
A Kinetic Heap is a kinetic data structure, obtained by the kinetization of a heap. It is designed to store elements (keys associated with priorities) 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 is a child node of , then the priority of the element in must be higher than the priority of the element in . This heap property is enforced using certificates along every edge so, like other kinetic data structures, a kinetic heap also contains a priority queue (the event queue) to maintain certificate failure times. Implementation and operations A regular heap can be kinetized by augmenting with a certificate [] for every pair of nodes, such that is a child node of . If the value stored at a node is a function of time, then this certificate is only ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kinetic Convex Hull
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. The 2D case The best known data structure for the 2-dimensional kinetic convex hull problem is by Basch, Guibas, and Hershberger. This data structure is responsive, efficient, compact and local. The data structure The dual of a convex hull of a set of points is the upper and lower envelopes of the dual set of lines. Therefore, maintaining the upper and lower envelopes of a set of moving lines is equivalent to maintaining the convex hull of a set of moving points. Computing upper and lower envelopes are equivalent problems, so computing the upper envelope of a set of lines is equivalent to computing the convex hull of a set of moving points. The upper envelo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kinetic Closest Pair
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 Kinetic data structure#Performance, efficient algorithms were known in the static case, they proved hard to Kinetic data structure#Certificates Approach, kinetize, so new static algorithms were developed to solve this problem. 2D case Approach 1 The simplest kinetic approach for maintenance of the closest pair is to use variants of the Delaunay triangulations. Consider a hexagon and partition it into six equilateral triangles, and then create a Delaunay triangulation based on each equilateral triangle, as each one is a convex shape. The union of these six Delaunay triangulations, so called Equilateral Delaunay graph (EDG), is a supergraph for the nearest neighbor graph (NNG); the endpoints of the edge with minimum length in EDG gives the closest pair. It is straightf ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kinetic Minimum Spanning Tree
A kinetic minimum spanning tree is a kinetic data structure that maintains the minimum spanning tree (MST) of a graph whose edge weights are changing as a continuous function of time. General case The most efficient known data structure for the general case uses a kinetic sorted list to store the edge weights, and a standard MST algorithm to compute the MST given the sorted edge weights. This data structure must process O(n^2) events, developing a more efficient data structure remains an open problem. H-minor-free graphs Agarwal ''et al.'' developed a data structure that maintains the MST for a graph belonging to a minor closed family. It uses the idea of a "swap", calculating the amount by which the weight of the MST would increase if some edge in the tree was replaced by an edge outside the tree such that the circle induced by in the tree contains . Maintaining the tree is then equivalent to finding and swapping the next pair for which this quantity becomes negativ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kinetic Euclidean Minimum Spanning Tree
A kinetic Euclidean minimum spanning tree is a kinetic data structure that maintains the Euclidean minimum spanning tree (EMST) of a set ''P'' of ''n'' points that are moving continuously. For the set of points ''P'' in 2-dimensional space, there are two kinetic algorithms for maintenance of the EMST. Rahmati and Zarei build a kinetic data structure based on the kinetic Delaunay triangulation to handle updates to the EMST in polylog time per event. Their kinetic data structure handles O(n*m) events, where m is the number of all changes to the Delaunay triangulation of the moving points. Their kinetic approach can work well for maintenance of the minimum spanning tree (MST) of a planar graph whose edge weights are changing as a continuous function of time. Abam, Rahmati, and Zarei provide a significant improvement on exact kinetic maintenance on the Euclidean minimum spanning tree A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-di ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
