|
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 of ... [...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] |
Diameter
In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid for the diameter of a sphere. In more modern usage, the length d of a diameter is also called the diameter. In this sense one speaks of diameter rather than diameter (which refers to the line segment itself), because all diameters of a circle or sphere have the same length, this being twice the radius r. :d = 2r \qquad\text\qquad r = \frac. For a convex shape in the plane, the diameter is defined to be the largest distance that can be formed between two opposite parallel lines tangent to its boundary, and the is often defined to be the smallest such distance. Both quantities can be calculated efficiently using rotating calipers. For a curve of constant width such as the Reuleaux triangle, the width and diameter are the same because all ... [...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 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] |
Antipodal Points
In mathematics, antipodal points of a sphere are those diametrically opposite to each other (the specific qualities of such a definition are that a line drawn from the one to the other passes through the center of the sphere so forms a true diameter). This term applies to opposite points on a circle or any n-sphere. An antipodal point is sometimes called an antipode, a back-formation from the Greek loan word ''antipodes'', meaning "opposite (the) feet", as the true word singular is ''antipus''. Theory In mathematics, the concept of ''antipodal points'' is generalized to spheres of any dimension: two points on the sphere are antipodal if they are opposite ''through the centre''; for example, taking the centre as origin, they are points with related vectors v and −v. On a circle, such points are also called diametrically opposite. In other words, each line through the centre intersects the sphere in two points, one for each ray out from the centre, and these two po ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Convex Hull
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. Convex hulls of open sets are open, and convex hulls of compact sets are compact. Every compact convex set is the convex hull of its extreme points. The convex hull operator is an example of a closure operator, and every antimatroid can be represented by applying this closure operator to finite sets of points. The algorithmic problems of finding the convex hull of a finite set of points in the plane or other low-dimensional Euclidean spaces, and its dual problem of intersecting half-spaces, are fundamental problems of com ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Supporting Line
In geometry, a supporting line ''L'' of a curve ''C'' in the plane is a line that contains a point of ''C'', but does not separate any two points of ''C''."The geometry of geodesics", Herbert Busemannp. 158/ref> In other words, ''C'' lies completely in one of the two closed half-planes defined by ''L'' and has at least one point on ''L''. Properties There can be many supporting lines for a curve at a given point. When a tangent exists at a given point, then it is the unique supporting line at this point, if it does not separate the curve. Generalizations The notion of supporting line is also discussed for planar shapes. In this case a supporting line may be defined as a line which has common points with the boundary of the shape, but not with its interior."Encyclopedia of Distances", by Michel M. Deza, Elena Dezap. 179/ref> The notion of a supporting line to a planar curve or convex shape can be generalized to n dimension as a supporting hyperplane. Critical support lines If tw ... [...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] |
Lower Envelope
In mathematics, the lower envelope or pointwise minimum of a finite set of functions is the pointwise minimum of the functions, the function whose value at every point is the minimum of the values of the functions in the given set. The concept of a lower envelope can also be extended to partial functions by taking the minimum only among functions that have values at the point. The upper envelope or pointwise maximum is defined symmetrically. For an infinite set of functions, the same notions may be defined using the infimum in place of the minimum, and the supremum in place of the maximum. For continuous functions from a given class, the lower or upper envelope is a piecewise function whose pieces are from the same class. For functions of a single real variable whose graphs have a bounded number of intersection points, the complexity of the lower or upper envelope can be bounded using Davenport–Schinzel sequences, and these envelopes can be computed efficiently by a divide-and-co ... [...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 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 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] |
