|
Kinetic Minimum Box
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. 2D case The 2D kinetic minimum box builds on the 2D kinetic convex hull in a manner similar to the kinetic width data structure which maintains the pair of minimum-distance parallel lines that have the entire point set between them. In this case, since a box consists of two pairs of parallel lines (that are perpendicular to each other), analogy can be made with running two perpendicular kinetic width problems, and the data-structure needs to maintain sets of four points two antipodal pairs which have perpendicular supporting lines. In the dual view where a point maps to a line , four envelopes (left, right, upper, lower) are computed. The range in x-values of a lin ... [...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 stru ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Minimum Bounding Box
In geometry, the minimum or smallest bounding or enclosing box for a point set in dimensions is the box with the smallest measure (area, volume, or hypervolume in higher dimensions) within which all the points lie. When other kinds of measure are used, the minimum box is usually called accordingly, e.g., "minimum-perimeter bounding box". The minimum bounding box of a point set is the same as the minimum bounding box of its convex hull, a fact which may be used heuristically to speed up computation. The terms "box" and "hyperrectangle" come from their usage in the Cartesian coordinate system, where they are indeed visualized as a rectangle (two-dimensional case), rectangular parallelepiped (three-dimensional case), etc. In the two-dimensional case it is called the minimum bounding rectangle. Axis-aligned minimum bounding box The axis-aligned minimum bounding box (or AABB) for a given point set is its minimum bounding box subject to the constraint that the edges of the box are ... [...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 Width
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. 2D case Consider the parallel lines which contain the point set in the strip between them and are of minimal distance apart. One of the lines must contain an edge ab of the convex hull, and the other line must go through a point c of the convex hull such that (a,c) and (b,c) are antipodal pairs. ab and c are referred to as an antipodal edge-vertex pair. Consider the dual of the point set. The points dualize to lines and the convex hull of the points dualizes to the upper and lower envelope of the set of lines. The vertices of the upper ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Antipodal Pairs
Antipode or Antipodes may refer to: Mathematics * Antipodal point, the diametrically opposite point on a circle or ''n''-sphere, also known as an antipode * Antipode, the convolution inverse of the identity on a Hopf algebra Geography * Antipodes, points on the Earth's surface that are diametrically opposed * Antipodes Islands, inhospitable volcanic islands south of New Zealand * Antipodes, a term for Australia and New Zealand, roughly the area known as Australasia, based on their rough proximity to the antipodes of Britain Arts and media * ''Antipode'' (journal), progressive social science general * ''Antipodes'' (sculpture) by Jim Sanborn * ''The Antipodes'', a c. 1640 stage play by Richard Brome * ''Antipodes'', journal of the American Association for Australian Literary Studies * Risley (circus act), a circus skill that involves juggling with one's feet while lying on one's back, also known as antipode Other uses * Antipode or Abarimon, mythical creature with feet turned ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Duality (projective Geometry)
In geometry, a striking feature of projective planes is the symmetry of the roles played by points and lines in the definitions and theorems, and (plane) duality is the formalization of this concept. There are two approaches to the subject of duality, one through language () and the other a more functional approach through special mappings. These are completely equivalent and either treatment has as its starting point the axiomatic version of the geometries under consideration. In the functional approach there is a map between related geometries that is called a ''duality''. Such a map can be constructed in many ways. The concept of plane duality readily extends to space duality and beyond that to duality in any finite-dimensional projective geometry. Principle of duality A projective plane may be defined axiomatically as an incidence structure, in terms of a set of ''points'', a set of ''lines'', and an incidence relation that determines which points lie on which lines. Th ... [...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 Priority Queue
A Kinetic Priority Queue is an abstract kinetic data structure. It is a variant of a priority queue designed to maintain the maximum (or minimum) priority element (key-value pair) 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. Implementations The operations supported are: * : create an empty kinetic priority queue * (or find-min): - return the (or for a ) value stored in the queue at the current virtual time . * : - insert a key into the kinetic queue at the current virtual time, whose value changes as a continuous function of time . * - delete a key at the current virtual time . There are several variants of kinetic priority queues, which support the same basic operations but have different performance guarante ... [...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 stru ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kinetic Data Structures
Kinetic (Ancient Greek: κίνησις “kinesis”, movement or to move) may refer to: * Kinetic theory, describing a gas as particles in random motion * Kinetic energy, the energy of an object that it possesses due to its motion Art and entertainment * Kinetic art, a form of art involving mechanical and/or random movement, including optical illusions. * ''Kinetic'', the 13th episode of the first season of the TV series ''Smallville'' * ''Kinetic'' (comics), a comic by Allan Heinberg and Kelley Pucklett * "Kinetic" (song), a song by Radiohead Companies * Kinetic Engineering Limited, Indian automotive manufacturer * Kinetic Group, Australian-based public transport company Technology * "Kinetic", Seiko's trademark for its automatic quartz technology * The ''Kinetic camera system'' by Birt Acres (1854–1918), photographer and film pioneer * Kinetic projectile Military terminology * Kinetic military action See also * * * Kinetics (other) * Dynamics (disambigu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
