Misplaced Pages

Kinetic triangulation

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

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.

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 Ω ( n 2 ) {\displaystyle \Omega (n^{2})} , thus the number of changes to any triangulation is also lower bounded by Ω ( n 2 ) {\displaystyle \Omega (n^{2})} . Finding any triangulation scheme that has a near-quadratic bound on the number of discrete changes is an important open problem.

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; it has now been bounded to be between Ω ( n 2 ) {\displaystyle \Omega (n^{2})} and O ( n 2 + ϵ ) {\displaystyle O(n^{2+\epsilon })} .

There is a kinetic data structure that efficiently maintains the Delaunay triangulation of a set of moving points, in which the ratio of the total number of events to the number of external events is O ( 1 ) {\displaystyle O(1)} .

Other triangulations

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

Pseudo-triangulations

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

References

  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.
  2. Sharir, M.; Agarwal, P. K. (1995). Davenport-Schinzel sequences and their geometric applications. New York: Cambridge University Press.
  3. Demaine, E.D.; Mitchell, J. S. B.; O’Rourke, J. "The Open Problems Project". Retrieved May 19, 2012.
  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.
  5. Rubin, Natan (June 2015). "On Kinetic Delaunay Triangulations: A Near-Quadratic Bound for Unit Speed Motions". J ACM. ACM. doi:10.1145/2746228. S2CID 2493978.
  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.
Categories: