Approximate Minimum Spanning Tree For Points Moving In A Euclidean Two-Dimensions Plane

摘要

We have proposed an algorithm for maintaining an approximate EMST for points moving in 2D-Euclidean plane. Although, efficiency and responsiveness are more important metrics of KDS, but our approach is only local and compact. We can make it responsive by using some extra space for storing the approximate EMST in such a way, such that the cycle can be detected in less than O(n) time. The datastructure used in our algorithm do not require any central storage. It performs in the same way if it is distributed over the points. Thus, this algorithm can also be used to find an EMST for independent objects in motion having autonomous processing capabilities.