Kinetic width

Last updated April 14, 2019

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 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 $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.$

A kinetic convex hull data structure is a kinetic data structure that maintains the convex hull of a set of continuously moving points.

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 convex hull dualize to segments on the upper envelope. The vertices of the lower convex hull dualize to segments on the lower envelope. The range of slopes of the supporting lines of a point on the hull dualize to the x-interval of segment that point dualizes to. When viewed in this dualized fashion the antipodal pairs, are pairs of segments, one from the upper envelope, one from the lower, with overlapping x ranges. Now, the upper and lower envelopes can be viewed as two different x-ordered lists of non overlapping intervals. If these two lists are merged, the antipodal pairs are the overlaps in the merged list. If a pair $ab$ and c is an antipodal edge-vertex pair, then the x-interval for a and b must both intersect the x-interval for c. This means that the common endpoint of the x intervals for a and b must lie within the x-interval for c.

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.

The endpoints of both of the sets of x-intervals can be maintained in a kinetic sorted list. When points swap, the list of antipodal edge-point pairs are updated appropriately. The upper and lower envelopes can be maintained using the standard data structure for kinetic convex hull. The minimum distance between edge-point pairs can be maintained with a kinetic tournament. Thus, using kinetic convex hull to maintain the upper and lower envelopes, a kinetic sorted list on these intervals to maintain the antipodal edge-vertex pairs, and a kinetic tournament to maintain the pair of minimum distance apart, the diameter of a moving point set can be maintained.

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 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.

This data structure is responsive, compact and efficient. The data structure uses $O(n)$ space because the kinetic convex hull, sorted list, and tournament data structures all use $O(n)$ space. In all of the data structures, events, inserts, and deletes can be handled in $O(\log ^{2}n)$ time, so the data structure are responsive, requiring $O(\log ^{2}n)$ per event. The data structure is efficient because the total number of events is $O(n^{2+\epsilon })$ for all $\epsilon >0$ and the width of a point set can change $\Omega (n^{2})$ times, even if the points are moving linearly. This data structure is not local because one point may be in many antipodal edge-vertex pairs, and thus appear many times in the kinetic tournament.

The existence of a local kinetic data structure for width is open.

Higher Dimensions

Efficiently maintaining the kinetic width of a point set in dimensions higher than 2 is an open problem. Efficient kinetic convex hull in dimensions higher than 2 is also an open problem.^[1]

Related Research Articles

Cube A geometric shape with 6 square faces

In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex.

In geometry, any polyhedron is associated with a second dual figure, where the vertices of one correspond to the faces of the other and the edges between pairs of vertices of one correspond to the edges between pairs of faces of the other. Such dual figures remain combinatorial or abstract polyhedra, but not all are also geometric polyhedra. Starting with any given polyhedron, the dual of its dual is the original polyhedron.

In mathematics and computational geometry, a Delaunay triangulation for a given set P of discrete points in a plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934.

In mathematics, the convex hull or convex envelope or convex closure of a set X of points in the Euclidean plane or in a Euclidean space is the smallest convex set that contains X. For instance, when X is a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around X.

Graham's scan is a method of finding the convex hull of a finite set of points in the plane with time complexity O(n log n). It is named after Ronald Graham, who published the original algorithm in 1972. The algorithm finds all vertices of the convex hull ordered along its boundary. It uses a stack to detect and remove concavities in the boundary efficiently.

Convex polytope convex hull of a finite set of points in a Euclidean space

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set of points in the n-dimensional space Rⁿ. Some authors use the terms "convex polytope" and "convex polyhedron" interchangeably, while others prefer to draw a distinction between the notions of a polyhedron and a polytope.

The Kirkpatrick–Seidel algorithm, called by its authors "the ultimate planar convex hull algorithm", is an algorithm for computing the convex hull of a set of points in the plane, with $time complexity, where is the number of input points and is the number of points in the hull. Thus, the algorithm is output-sensitive: its running time depends on both the input size and the output size. Another output-sensitive algorithm, the gift wrapping algorithm, was known much earlier, but the Kirkpatrick-Seidel algorithm has an asymptotic running time that is significantly smaller and that always improves on the bounds of non-output-sensitive algorithms. The Kirkpatrick-Seidel algorithm is named after its inventors, David G. Kirkpatrick and Raimund Seidel.$

Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science.

In computer science, a range tree is an ordered tree data structure to hold a list of points. It allows all points within a given range to be reported efficiently, and is typically used in two or higher dimensions. Range trees were introduced by Jon Louis Bentley in 1979. Similar data structures were discovered independently by Lueker, Lee and Wong, and Willard. The range tree is an alternative to the k-d tree. Compared to k-d trees, range trees offer faster query times of $but worse storage of, where n is the number of points stored in the tree, d is the dimension of each point and k is the number of points reported by a given query.$

In computational geometry, the method of rotating calipers is an algorithm design technique that can be used to solve optimization problems including finding the width or diameter of a set of points.

In computational geometry, a CC system or counterclockwise system is a ternary relation $pqr$ introduced by Donald Knuth to model the clockwise ordering of triples of points in general position in the Euclidean plane.

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 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 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 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.

References

↑ Guibas, Leonidas J. (2001), "Kinetic Data Structures" (PDF), in Mehta, Dinesh P.; Sahni, Sartaj, Handbook of Data Structures and Applications, Chapman and Hall/CRC, pp. 23–1–23–18, ISBN 978-1584884354

Kinetic width

Contents

2D case

Higher Dimensions

Related Problems

Related Research Articles

References

Further reading