Combinatorial Changes of Euclidean Minimum Spanning Tree of Moving Points in the Plane
Zahed Rahmati, Alireza Zarei · 2010
In this paper, we enumerate the number of combinatorial changes of the the Euclidean minimum spanning tree (EMST) of a set of n moving points in 2-dimensional space. We assume that the motion of the points in the plane, is defined by algebraic functions of maximum degree s of time. We prove an upper bound of O(n 3 β2s(n 2)) for the number of the combinatorial changes of the EMST, where βs(n)=λs(n)/n and λs(n) is the maximum length of Davenport-Schinzel sequences of order s on n symbols which is nearly linear in n. This result is an O(n) improvement over the previously trivial bound of O(n 4). 1