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 [math]\displaystyle{ \Omega(n^2) }[/math],[2] thus the number of changes to any triangulation is also lower bounded by [math]\displaystyle{ \Omega(n^2) }[/math]. 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 [math]\displaystyle{ \Omega(n^2) }[/math][4] and [math]\displaystyle{ O(n^{2+\epsilon}) }[/math].[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 [math]\displaystyle{ O(1) }[/math].
Other triangulations
Kaplan et al. developed a randomized triangulation scheme that experiences an expected number of [math]\displaystyle{ O(n^2 \beta_{s+2}(n) \log^2 n) }[/math] external events, where [math]\displaystyle{ s }[/math] is the maximum number of times each triple of points can become collinear, [math]\displaystyle{ \beta_{s+2}(q) = \frac{\lambda_{s+2}(q)}{q} }[/math], and [math]\displaystyle{ \lambda_{s+2}(q) }[/math] 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 [math]\displaystyle{ O(n^22^{\sqrt{\log n\log\log n}}) }[/math] events total.[7] All events are external and require [math]\displaystyle{ O(\lg n) }[/math] time to process.
References
- ↑ 1.0 1.1 1.2 Kaplan, Haim; Rubin, Natan; Sharir, Micha (June 2010). "A Kinetic Triangulation Scheme for Moving Points in The Plane". SCG. ACM. http://www.math.tau.ac.il/~michas/triank.pdf. Retrieved May 19, 2012.
- ↑ Sharir, M.; Agarwal, P. K. (1995). Davenport-Schinzel sequences and their geometric applications. New York: Cambridge University Press.
- ↑ "The Open Problems Project". http://www.cs.smith.edu/~orourke/TOPP/. 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. [1]
 |  |
