# On minimum and maximum spanning trees of linearly moving points

## Abstract

In this paper we investigate the upper bounds on the numbers of transitions of minimum and maximum spanning trees (MinST and MaxST for short) for linearly moving points. Here, a transition means a change on the combinatorial structure of the spanning trees. Suppose that we are given a set of n points in d-dimensional space, S={p 1, p 2, ... p n }, and that all points move along different straight lines at different but fixed speeds, i.e., the position of p i is a linear function of a real parameter t. We investigate the numbers of transitions of MinST and MaxST when t increases from-∞ to +∞. We assume that the dimension d is a fixed constant. Since there are O(n 2) distances among n points, there are naively O(n 4) transitions of MinST and MaxST. We improve these trivial upper bounds for L 1 and L ∞ distance metrics. Let k p (n) (resp.[Figure not available: see fulltext.]) be the number of maximum possible transitions of MinST (resp. MaxST) in L p metric for n linearly moving points. We give the following results in this paper: κ1(n)=O(n 5/2 α(n)), κ ∞(n)=O(n 5/2 α(n)),[Figure not available: see fulltext.], and[Figure not available: see fulltext.] where α(n) is the inverse Ackermann's function. We also investigate two restricted cases, i.e., the c-oriented case in which there are only c distinct velocity vectors for moving n points, and the case in which only k points move. © 1995 Springer-Verlag New Inc.