Misplaced Pages

Kinetic Euclidean minimum spanning tree

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 Euclidean minimum spanning tree is a kinetic data structure that maintains the Euclidean minimum spanning tree (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 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 minimum spanning tree (MST) of a planar graph 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. Their kinetic data structure handles a nearly cubic number of events.

References

  1. Rahmati, Zahed; Zarei, Alireza (2012). "Kinetic Euclidean minimum spanning tree in the plane". Journal of Discrete Algorithms. 16: 2–11. doi:10.1016/j.jda.2012.04.009.
  2. Ali Abam, Mohammad; Rahmati, Zahed; Zarei, Alireza (2012). "Kinetic Pie Delaunay Graph and Its Applications". Algorithm Theory – SWAT 2012. Lecture Notes in Computer Science. Vol. 2012. pp. 48–58. doi:10.1007/978-3-642-31155-0_5. ISBN 978-3-642-31154-3.
Category:
Kinetic Euclidean minimum spanning tree Add topic