A kinetic Euclidean minimum spanning tree is a
kinetic data structure that maintains the
Euclidean minimum spanning tree
A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. ...
(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
polylog time per event. Their kinetic data structure handles
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
minimum spanning tree
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...
(MST) of a
planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...
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
Euclidean minimum spanning tree
A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. ...
. Their kinetic data structure handles a nearly cubic number of events.
References
{{Reflist , refs=
[{{cite journal , last1 = Rahmati , first1 = Zahed , last2 = Zarei , first2 = Alireza , year = 2012 , title = Kinetic Euclidean minimum spanning tree in the plane , journal = Journal of Discrete Algorithms , volume = 16 , pages = 2–11 , doi = 10.1016/j.jda.2012.04.009 , doi-access = free ]
[{{cite book , last1 = Ali Abam , first1 = Mohammad , last2 = Rahmati , first2 = Zahed , last3 = Zarei , first3 = Alireza , title = Algorithm Theory – SWAT 2012 , chapter = Kinetic Pie Delaunay Graph and Its Applications , year = 2012 , series = Lecture Notes in Computer Science , volume = 2012 , pages = 48–58 , doi = 10.1007/978-3-642-31155-0_5 , isbn = 978-3-642-31154-3 ]
Kinetic data structures