Kinetic triangulation explained

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

\Omega(n²⁾

, thus the number of changes to any triangulation is also lower bounded by

\Omega(n²⁾

. 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

\Omega(n²⁾

and

O(n^2+\epsilon)

There is a kinetic data structure that efficiently maintains the Delaunay triangulation of a set of moving points,^[1]

Notes and References

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