About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
FOCS 1992
Conference paper
On minimum and maximum spanning trees of linearly moving points
Abstract
The authors investigate the upper bounds on the numbers of transitions of minimum and maximum spanning trees (MinST and MaxST for short) for linearly moving points. Suppose that one is given a set of n points in general d-dimensional space, S=(p1,p2,..., pn), and that all points move along different straight lines at different but fixed speeds, i.e., the position of pi is a linear function of a real parameter. They investigate the numbers of transitions of MinST and MaxST when t increases from - infinity to + infinity. They assume that the dimension d is a fixed constant. Since there are O(n2) distances among n points, there are naively O(n4) transitions of MinST and MaxST. They improve these trivial upper bounds for L1 and L/sub infinity / distance metrics. Let cp(n, min) (resp. cp(n, max)) be the number of maximum possible transitions of MinST (resp. MaxST) in Lp metric for n linearly moving points. They give the following results; c1(n, min)=O(n5/2a(n)), c/sub infinity /(n, min)=O(n5/2a(n)), c1(n, max)=O(nn) and c/sub infinity /(n, max)=O(n2) where O(n) is the inverse Ackermann function. They also investigate two restricted cases.