Árbol de expansión mínima euclidiano cinético

Un árbol de expansión mínima euclidiana cinético es una estructura de datos cinética que mantiene el árbol de expansión mínima euclidiana (EMST) de un conjunto P de n puntos que se mueven continuamente.

Para el conjunto de puntos P en un espacio bidimensional, existen dos algoritmos cinéticos para el mantenimiento del EMST.

Rahmati y Zarei ^{[ 1 ]} construyen una estructura de datos cinética basada en la triangulación de Delaunay cinética para manejar actualizaciones del EMST en tiempo polilogarítmico por evento. Su estructura de datos cinética maneja${\displaystyle O(n*m)}$eventos, donde m es el número de todos los cambios en la triangulación de Delaunay de los puntos móviles. Su enfoque cinético puede funcionar bien para el mantenimiento del árbol de expansión mínima (MST) de un grafo planar cuyos pesos de aristas cambian como una función continua del tiempo.

Abam, Rahmati y Zarei ^{[ 2 ]} proporcionan una mejora significativa en el mantenimiento cinético exacto en el árbol de expansión mínima euclidiana . Su estructura de datos cinéticos maneja un número de eventos casi cúbico.