Kinetic triangulation

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 analysis of the number of discrete changes that will occur to the Delaunay triangulation (external events) is one of the hardest problems in computational geometry,^[3] and the best currently known upper bound is $O(n^{3})$ .

There is a kinetic data structure that efficiently maintains the Delaunay triangulation of a set of moving points,^[4] 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.^[5] All events are external and require $O(\lg n)$ time to process.

References

^ ^a ^b ^c 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.{{cite book}}: CS1 maint: extra punctuation (link) CS1 maint: multiple names: authors list (link)
^ Demaine, E.D.; Mitchell, J. S. B.; O’Rourke, J. "The Open Problems Project". Retrieved May 19, 2012.
^ 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. [1]

Pankaj K. Agarwal, Julien Basch, Mark de Berg, Leonidas J. Guibas, and John Hershberger. Lower bounds for kinetic planar subdivisions. In SCG '99: Proceedings of the fifteenth annual symposium on Computational geometry, pages 247{254, New York, NY, USA, 1999. ACM.[2]

[micha-1] 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.{{cite book}}: CS1 maint: extra punctuation (link) CS1 maint: multiple names: authors list (link)

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

[4] 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.

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

[1]

[2]

[3]

[4]

[5]