Kinetic Euclidean minimum spanning tree

A kinetic Euclidean minimum spanning tree is a <a href="/facts/Kinetic_data_structure/410CqBg7">kinetic data structure</a> that maintains the <a href="/facts/Euclidean_minimum_spanning_tree/yu6atHA6">Euclidean minimum spanning tree</a> (EMST) of a set P of n points that are moving continuously.
For the set of points P in 2-dimensional space, there are two kinetic algorithms for maintenance of the EMST.
Rahmati and Zarei build a kinetic data structure based on the kinetic Delaunay triangulation to handle updates to the EMST in <a href="/facts/Polylogarithmic_time/77T62gmf">polylog time</a> per event. Their kinetic data structure handles 
 
 
 
 O
 (
 n
 ∗
 m
 )
 
 
 {\displaystyle O(n*m)}
 
 events, where m is the number of all changes to the Delaunay triangulation of the moving points. 
Their kinetic approach can work well for maintenance of the <a href="/facts/Minimum_spanning_tree/kgkGmY9s">minimum spanning tree</a> (MST) of a <a href="/facts/Planar_graph/plREagr9">planar graph</a> whose edge weights are changing as a continuous function of time.
Abam, Rahmati, and Zarei provide a significant improvement on exact kinetic maintenance on the <a href="/facts/Euclidean_minimum_spanning_tree/yu6atHA6">Euclidean minimum spanning tree</a>. Their kinetic data structure handles a nearly cubic number of events.

Kinetic Euclidean minimum spanning tree open-in-new

Kinetic Euclidean minimum spanning tree