Maintaining a Minimum Spanning Tree for Kinetic Autonomous Robots in 2D-Euclidean Plane

摘要

This paper presents a procedure for maintaining a 2D-Euclidean Minimum Spanning Tree for a set of n autonomous kinetic robots having no central supervision. The proposed procedure is based on the Kinetic data structure framework and the well known fact that the edges of the minimum spanning tree for a given set of points in the 2D-Euclidean domain are contained in the edges of its Delaunay triangulation. The kinetic data structure framework has a centralized data structure along with a priority queue on which a proposed algorithm works to maintain a combinatorial geometrical structure for a set of geometric objects. In this work, we propose an approach where the computation of the geometrical structure is done through the geometrical objects, in our case, the computations being done by the robots themselves. This is unlike that of maintaining a centralized data structure in the kinetic data structure framework. The kinetic autonomous robots, each being a computing object do all computations by themselves and update the spanning tree as the tree changes. In terms of kinetic data structure metrics, our data structure is local and compact.