Kinetic triangulation

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 ) , thus the number of changes to any triangulation is also lower bounded by Ω ( 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 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, 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, 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 β s + 2 ( n ) log 2 ⁡ n ) external events, where s is the maximum number of times each triple of points can become collinear, β s + 2 ( q ) = λ s + 2 ( q ) q , and λ 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 ) events total. All events are external and require O ( lg ⁡ n ) time to process.