Minimum spanning trees of moving points in the plane
- 1 January 1991
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 40 (1) , 113-118
- https://doi.org/10.1109/12.67328
Abstract
[[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]]資訊工程學Keywords
This publication has 11 references indexed in Scilit:
- Filtering Search: A New Approach to Query-AnsweringSIAM Journal on Computing, 1986
- AnO(N logN) minimal spanning tree algorithm forN points in the planeBIT Numerical Mathematics, 1986
- Biased Search TreesSIAM Journal on Computing, 1985
- Priority Search TreesSIAM Journal on Computing, 1985
- Computational GeometryPublished by Springer Nature ,1985
- A data structure for dynamic treesJournal of Computer and System Sciences, 1983
- Plane-sweep algorithms for intersecting geometric figuresCommunications of the ACM, 1982
- Ein rekursiver Gleitebenen-Algorithmus für die Bestimmung aller Zellen einer endlichen Teilung des RdComputing, 1982
- An Optimal Worst Case Algorithm for Reporting Intersections of RectanglesIEEE Transactions on Computers, 1980
- On the Shortest Spanning Subtree of a Graph and the Traveling Salesman ProblemProceedings of the American Mathematical Society, 1956