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 ofn points ind-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 ofp i is a linear function of a real parametert. We investigate the numbers of transitions of MinST and MaxST whent increases from-∞ to +∞. We assume that the dimensiond is a fixed constant. Since there areO(n 2) distances amongn points, there are naivelyO(n 4) transitions of MinST and MaxST. We improve these trivial upper bounds forL 1 andL ∞ distance metrics.
Letk p (n) (resp.
) be the number of maximum possible transitions of MinST (resp. MaxST) inL p metric forn linearly moving points. We give the following results in this paper: κ1(n)=O(n 5/2 α(n)),κ ∞(n)=O(n 5/2 α(n)),
, and
where α(n) is the inverse Ackermann's function. We also investigate two restricted cases, i.e., thec-oriented case in which there are onlyc distinct velocity vectors for movingn points, and the case in which onlyk points move.
Article PDF
Similar content being viewed by others
References
P. K. Agarwal, M. Sharir, and P. Shor, Sharp Upper and Lower Bounds on the Length of General Davenport-Schinzel Sequences,J. Combin. Theory Ser. A.,52(2) (1989), 228–274.
N. M. Amato, and F. P. Preparata, The Parallel 3D Convex Hull Problem Revisited,Internat. J. Comput. Geom. Appl.,2(1992), 163–173.
B. Aronov, M. Bern, and D. Eppstein, Number of Minimal 1-Steiner Trees,Discrete Comput. Geom.,12(1) (1994), 29–34.
M. J. Atallah, Some Dynamic Computational Geometry Problems,Comput. Math. Appl.,11 (1985), 1171–1181.
L. P. Chew, Near Quadratic Bounds for theL 1 Voronoi Diagram of Moving Points,Proc. 5th Canadian Conference on Computational Geometry, 1993, pp. 364–369.
H. Edelsbrunner,Algorithms in Combinatorial Geometry, ETACS Monograph on Theoretical Computer Science, Vol. 10, Springer-Verlag, Berlin, 1987.
J. J. Fu, and R. C. T. Lee, Voronoi Diagrams of Moving Points in the Plane,Internat. J. Comput. Geom. Appl.,1(1) (1991), 23–32.
L. Guibas, J. Mitchell, and T. Roos, Voronoi Diagrams of Moving Points in the Plane,Proc. 17th International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS, Vol. 570, Springer-Verlag, Berlin, pp. 113–125.
D. Gusfield, Bounds for the Parametric Spanning Tree Problem,Proc. Humbolt Conference on Graph Theory, Combinatorics and Computing, Utilitas Mathematica, Winnipeg, 1979, pp. 173–183.
S. Hart, and M. Sharir, Nonlinearity of Davenport-Schinzel Sequences and of Generalized Path Compression,Combinatorica,6, (1986), 151–177.
H. Imai and K. Imai, Voronoi Diagrams of Moving Points,Proc. International Computer Symposium, Taiwan, 1990, pp. 600–606.
N. Katoh and T. Ibaraki, On the Total Number of Pivots Requred for Certain Parametric Combinatorial Optimization Problems, Working Paper No. 71, Institute of Economic Research, Kobe University of Commerce, 1983.
N. Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms,J. Assoc. Comput. Math.,30 (1983), 852–865.
C. Monma, M. Paterson, S. Suri, and F. Yao, Computing Euclidean Maximum Spanning Trees,Proc. 4th ACM Symposium on Computational Geometry, 1988, pp. 241–251.
C. Monma and S. Suri, Transitions, in Geometric Minimum Spanning Trees,Proc. 7th ACM Symposium on Computational Geometry, 1991, pp. 239–249.
R. E. Tarjan,Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, Vol. 44, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983.
T. Tokuyama, Unpublished result.
D. J. A. Welsh,Matroid Theory, Academic Press, London, 1976.
A. Wiernik, and M. Sharir, Planar Realization of Nonlinear Davenport-Schinzel Sequences by Segments,Discrete Comput. Geom.,3 (1988), 15–47.
A. C. Yao, On Constructing Minimum Spanning Trees ink-Dimensional Space and Related Problems,SIAM J. Comput.,11 (1982), 721–736.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Katoh, N., Tokuyama, T. & Iwano, K. On minimum and maximum spanning trees of linearly moving points. Discrete Comput Geom 13, 161–176 (1995). https://doi.org/10.1007/BF02574035
Received:
Revised:
Published:
Issue date:
DOI: https://doi.org/10.1007/BF02574035
