Kinetic Euclidean minimum spanning tree

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[1] 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) 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[2] 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. ↑ Zahed Rahmati, Alireza Zarei. Kinetic Euclidean minimum spanning tree in the plane. Journal of Discrete Algorithms, 16, pp. 2-11, 2012. http://dx.doi.org/10.1016/j.jda.2012.04.009
  2. ↑ Mohammad Ali Abam, Zahed Rahmati, Alireza Zarei. Kinetic Pie delaunay graph and its applications. Algorithm Theory–SWAT 2012, pp. 48-58, 2012. DOI: 10.1007/978-3-642-31155-0_5
This article is issued from Wikipedia - version of the Sunday, May 11, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.