Kinetic Euclidean Minimum Spanning Tree in the Plane

摘要

This paper presents the first kinetic data structure (KDS) for maintenance of the Euclidean minimum spanning tree (EMST) on a set of n moving points in 2-dimensional space. We build a KDS of size O(n) in O(n log n) preprocessing time by which their EMST is main tained efficiently during the motion. In terms of the KDS performance parameters, our KDS is responsive, local, and compact.