Minimum Spanning Trees of Moving Points in the Plane

[[abstract]]In this paper, we consider the following problem. Preprocess n moving points in the plane, such that the Euclidean minimum spanning tree of these points at a given time t can be reported efficiently. In our result, if the moving points are in k-motion, after an O(kn4 log n) time preprocessing step, and using O(m) space to store the preprocessing result, the Euclidean minimum spanning tree at a given time t can be reported in O(n) time, where m denotes the number of changes of the Euclidean minimum spanning tree of these points from time t = 0 to time t = infinity.[[fileno]]2030256010044[[department]]資訊工程學