Kinetic triangulation

Last updated June 21, 2020

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.^[1]

Choosing a triangulation scheme

The efficiency of a kinetic data structure is defined based on the ratio of the number of internal events to external events, thus good runtime bounds can sometimes be obtained by choosing to use a triangulation scheme that generates a small number of external events. For simple affine motion of the points, the number of discrete changes to the convex hull is estimated by $\Omega (n^{2})$ ,^[2] thus the number of changes to any triangulation is also lower bounded by $\Omega (n^{2})$ . Finding any triangulation scheme that has a near-quadratic bound on the number of discrete changes is an important open problem.^[1]

Delaunay triangulation

The Delaunay triangulation seems like a natural candidate, but a tight worst-case analysis of the number of discrete changes that will occur to the Delaunay triangulation (external events) was considered an open problem until 2015;^[3] it has now been bounded to be between $\Omega (n^{2})$ ^[4] and $O(n^{2+\epsilon })$ .^[5]

There is a kinetic data structure that efficiently maintains the Delaunay triangulation of a set of moving points,^[6] in which the ratio of the total number of events to the number of external events is $O(1)$ .

Other triangulations

Kaplan et al. developed a randomized triangulation scheme that experiences an expected number of $O(n^{2}\beta _{s+2}(n)\log ^{2}n)$ external events, where $s$ is the maximum number of times each triple of points can become collinear, $\beta _{s+2}(q)={\frac {\lambda _{s+2}(q)}{q}}$ , and $\lambda _{s+2}(q)$ is the maximum length of a Davenport-Schinzel sequence of order s + 2 on n symbols.^[1]

Pseudo-triangulations

There is a kinetic data structure (due to Agarwal et al.) which maintains a pseudo-triangulation in $O(n^{2}2^{\sqrt {\log n\log \log n}})$ events total.^[7] All events are external and require $O(\lg n)$ time to process.

Related Research Articles

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.

Arrangement of lines partition of the plane formed by a collection of lines

In geometry an arrangement of lines is the partition of the plane formed by a collection of lines. Bounds on the complexity of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.

The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of n points in the plane, where the weight of the edge between each pair of points is the Euclidean distance between those two points. In simpler terms, an EMST connects a set of dots using lines such that the total length of all the lines is minimized and any dot can be reached from any other by following the lines.

A triangulation of a set of points $in the Euclidean space is a simplicial complex that covers the convex hull of, and whose vertices belong to . In the plane, triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of are vertices of its triangulations. In this case, a triangulation of a set of points in the plane can alternatively be defined as a maximal set of non-crossing edges between points of . In the plane, triangulations are special cases of planar straight-line graphs.$

The dynamic convex hull problem is a class of dynamic problems in computational geometry. The problem consists in the maintenance, i.e., keeping track, of the convex hull for input data undergoing a sequence of discrete changes, i.e., when input data elements may be inserted, deleted, or modified. It should be distinguished from the kinetic convex hull, which studies similar problems for continuously moving points. Dynamic convex hull problems may be distinguished by the types of the input data and the allowed types of modification of the input data.

In computational geometry, the visibility polygon or visibility region for a point p in the plane among obstacles is the possibly unbounded polygonal region of all points of the plane visible from p. The visibility polygon can also be defined for visibility from a segment, or a polygon. Visibility polygons are useful in robotics, video games, and in determining positions to locate facilities, such as the best placement of security guards in an art gallery.

Leonidas J. Guibas American computer scientist

Leonidas John Guibas is the Paul Pigott Professor of Computer Science and Electrical Engineering at Stanford University, where he heads the geometric computation group and is a member of the computer graphics and artificial intelligence laboratories.

In combinatorics, a Davenport–Schinzel sequence is a sequence of symbols in which the number of times any two symbols may appear in alternation is limited. The maximum possible length of a Davenport–Schinzel sequence is bounded by the number of its distinct symbols multiplied by a small but nonconstant factor that depends on the number of alternations that are allowed. Davenport–Schinzel sequences were first defined in 1965 by Harold Davenport and Andrzej Schinzel to analyze linear differential equations. Following Atallah (1985) these sequences and their length bounds have also become a standard tool in discrete geometry and in the analysis of geometric algorithms.

Kenneth Lee Clarkson is an American computer scientist known for his research in computational geometry. He is a researcher at the IBM Almaden Research Center, and co-editor-in-chief of the Journal of Computational Geometry.

In computational geometry and computer science, the minimum-weight triangulation problem is the problem of finding a triangulation of minimal total edge length. That is, an input polygon or the convex hull of an input point set must be subdivided into triangles that meet edge-to-edge and vertex-to-vertex, in such a way as to minimize the sum of the perimeters of the triangles. The problem is NP-hard for point set inputs, but may be approximated to any desired degree of accuracy. For polygon inputs, it may be solved exactly in polynomial time. The minimum weight triangulation has also sometimes been called the optimal triangulation.

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 Heap is a kinetic data structure, obtained by the kinetization of a heap. It is designed to store elements 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 $B$ is a child node of $A$ , then the priority of the element in $A$ must be higher than the priority of the element in $B$ . This heap property is enforced using certificates along every edge so, like other kinetic data structures, a kinetic heap also contains a priority queue to maintain certificate failure times.

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.

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

John E. Hershberger is an American computer scientist and software professional, a principal engineer at Mentor Graphics Corporation since 1993. He is known for his research in computational geometry and algorithm engineering.

In discrete geometry and computational geometry, the relative convex hull or geodesic convex hull is an analogue of the convex hull for the points inside a simple polygon or a rectifiable simple closed curve.

References

1 2 3 Kaplan, Haim; Rubin, Natan; Sharir, Micha (June 2010). A Kinetic Triangulation Scheme for Moving Points in The Plane (PDF). SCG. ACM. Retrieved May 19, 2012.
↑ Sharir, M.; Agarwal, P. K. (1995). Davenport-Schinzel sequences and their geometric applications. New York: Cambridge University Press.
↑ Demaine, E.D.; Mitchell, J. S. B.; O’Rourke, J. "The Open Problems Project" . Retrieved May 19, 2012.
↑ Agarwal, Pankaj K.; Basch, Julien; de Berg, Mark; Guibas, Leonidas J.; Hershberger, John (June 1999). Lower bounds for kinetic planar subdivisions. SCG. ACM. pp. 247–254. doi:10.1145/304893.304961.
↑ Rubin, Natan (June 2015). "On Kinetic Delaunay Triangulations: A Near-Quadratic Bound for Unit Speed Motions". J ACM. ACM. doi:10.1145/2746228.
↑ Gerhard Albers, Leonidas J. Guibas, Joseph S. B. Mitchell, and Thomas Roos. Voronoi diagrams of moving points. Int. J. Comput. Geometry Appl., 8(3):365{380, 1998.
↑ Pankaj K. Agarwal, Julien Basch, Leonidas J. Guibas, John Hershberger, and Li Zhang. Deformable free-space tilings for kinetic collision detection. I. J. Robotic Res., 21(3):179{198, 2002.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[micha-1] 1 2 3 Kaplan, Haim; Rubin, Natan; Sharir, Micha (June 2010). A Kinetic Triangulation Scheme for Moving Points in The Plane (PDF). SCG. ACM. Retrieved May 19, 2012.

[convex_hull-2] Sharir, M.; Agarwal, P. K. (1995). Davenport-Schinzel sequences and their geometric applications. New York: Cambridge University Press.

[delaunay_hardness-3] Demaine, E.D.; Mitchell, J. S. B.; O’Rourke, J. "The Open Problems Project" . Retrieved May 19, 2012.

[lower_bound-4] Agarwal, Pankaj K.; Basch, Julien; de Berg, Mark; Guibas, Leonidas J.; Hershberger, John (June 1999). Lower bounds for kinetic planar subdivisions. SCG. ACM. pp. 247–254. doi:10.1145/304893.304961.

[delaunay_bounded-5] Rubin, Natan (June 2015). "On Kinetic Delaunay Triangulations: A Near-Quadratic Bound for Unit Speed Motions". J ACM. ACM. doi:10.1145/2746228.

[6] Gerhard Albers, Leonidas J. Guibas, Joseph S. B. Mitchell, and Thomas Roos. Voronoi diagrams of moving points. Int. J. Comput. Geometry Appl., 8(3):365{380, 1998.

[7] Pankaj K. Agarwal, Julien Basch, Leonidas J. Guibas, John Hershberger, and Li Zhang. Deformable free-space tilings for kinetic collision detection. I. J. Robotic Res., 21(3):179{198, 2002.