Abstract
Consider a set of n points in the Euclidean plane each of which is continuously moving along a given trajectory. At each instant in time, the points define a Voronoi diagram. As the points move, the Voronoi diagram changes continuously, but at certain critical instants in time, topological events occur that cause a change in the Delaunay diagram. In this paper, we present a method of maintaining the Voronoi diagram over time, while showing that the number of topological events has a nearly cubic upper bound of O(n2λs(n)), where λs,(n) is the maximum length of an (n, s)-Davenport-Schinzel sequence and s is a constant depending on the motions of the point sites. In the special case of points moving at constant speed along straight lines, we get s = 4, implying an upper bound of O(n 32α(n)), where α(n) is the extremely slowly-growing inverse of Ackermann 's function. Our results are a linear-factor improvement over the naive quartic bound on the number of topological events.
In addition, we show that if only k points are moving (while leaving the other n− k points fixed), there is an upper bound of O(k n λs(n) + (n−k)2 λs(k)) on the number of topological events, which is nearly quadratic if k is constant.
We give a numerically stable algorithm for the update of the topological structure of the Voronoi diagram, using only O(log n) time per event (which is worst-case optimal per event).
Partially supported by a grant from Hughes Research Laboratories, Malibu, CA, and by NSF Grant ECSE-8857642.
Work on this paper by Thomas Roos was supported by the Deutsche Forschungsgemeinschaft (DFG) under contract (No 88/10-1).
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Abramowski and H. Müller, Collision Avoidance for Nonrigid Objects, in H. Noltemeier (ed.): ZOR — Zeitschrift für Operations Research, Vol. 32, 1988, pp 165–186
A. Aggarwal, L. Guibas, J. Saxe and P. Shor, A Linear Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon, Proc. of the 19th Annual ACM Symposium on Theory of Computing, New York City, 1987, pp 39–45
A. Aggarwal, M. Sharir and P. Shor, Sharp Upper and Lower Bounds on the Length of General Davenport-Schinzel Sequences, Journal of Combinatorial Theory, Series A, Vol. 52, 1989, pp 228–274
M.J. Atallah, Some Dynamic Computational Geometry Problems, Computers and Mathematics with Applications, Vol. 11, 1985, pp 1171–1181
H. Aunuma, H. Imai, K. Imai and T. Tokuyama, Maximin Locations of Convex Objects and Related Dynamic Voronoi Diagrams, Proc. of the 6th ACM Symposium on Computational Geometry, Berkeley, 1990, pp 225–234
F. Aurenhammer, Voronoi Diagrams — A Survey, Report 263, Nov. 1988, Institute für Informationsverarbeitung, Techn. Univ. Graz
B. Chazelle and H. Edelsbrunner, An Improved Algorithm for Constructing k th-Order Voronoi Diagrams, IEEE Transactions on Computers, Vol. C-36, Nov. 1987, No. 11, pp 1349–1354
R.L. Drysdale III and D.T. Lee, Generalized Voronoi Diagrams in the Plane, Proc. 16th Annual Allerton Conference on Communications, Control and Computing, Oct. 1978, pp 833–842
H. Edelsbrunner, Edge-Skeletons in Arrangements with Applications, Algorithmica 1986, Vol. 1, pp 93–109
H. Edelsbrunner, Algorithms in Combinatorial Geometry, EATCS Monographs in Computer Science, Springer-Verlag, Berlin-Heidelberg, 1987
H. Edelsbrunner, J. O'Rourke and R. Seidel, Constructing Arrangements of Lines and Hyperplanes with Applications, SIAM J. Comput., Vol. 15, No. 2, May 1986, pp 341–363
S. Fortune, A Sweep-line Algorithm for Voronoi Diagrams, Proc. 2nd Annual ACM Symp. Computational Geometry, Yorktown Heights, 1986, pp 313–322
J-J. Fu and R.C.T. Lee, Voronoi Diagrams of Moving Points in the Plane, Int. Journal of Computational Geometry & Applications, Vol. 1, No. 1, 1991, pp 23–32
H. Imai and K. Imai, Voronoi Diagrams of Moving Points, Proc. Int. Computer Symp., Taiwan, 1990, pp 600–606
I.G. Gowda, D.G. Kirkpatrick, D.T. Lee and A. Naamad, Dynamic Voronoi Diagrams, IEEE Trans. on Information Theory, Vol. IT-29, No. 5, Sept. 1983, pp 724–731
L. Guibas, D.E. Knuth and M. Sharir, Randomized Incremental Construction of Delaunay and Voronoi Diagrams, Proc. 17th Intern. Colloquium on Automata, Languages and Programming ICALP 90, LNCS 443, Springer, 1990, pp 414–431
L. Guibas and J. Stolfi, Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams, ACM Transactions on Graphics, Vol. 4, No. 2, April 1985, pp 74–123
H. Hadwiger und H. Debrunner, Kombinatorische Geometrie in der Ebene, Monographies de L'Enseignement Mathématique, No. 2, Université Genève, 1959
S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel Sequences and of Generalized Path Compression Schemes, Combinatorica, 1986, Vol. 6, pp 151–177
K. Imai, S. Sumino and H. Imai, Geometric Fitting of Two Corresponding Sets of Points, Proc. 5th ACM Symp. on Computational Geometry, 1989, pp 266–275
D.T. Lee, On k-Nearest Neighbor Voronoi Diagrams in the Plane, IEEE Transactions on Computers, Vol. C-31, No. 6, June 1982, pp 478–487
D. Leven and M. Sharir, Planning a Purely Translational Motion for Convex Objects in Two-Dimensional Space Using Generalized Voronoi Diagrams, Discrete & Computational Geometry, 1987, Vol. 2, pp 9–31
H. Noltemeier, Computational Geometry and its Applications, Proceedings Workshop CG '88, Universität Würzburg, März 1988, LNCS 333, Springer Verlag, 1988
J. O'Rourke, Computational Geometry Column 12, SIGACT News, Vol. 22, No. 2, Spring 1991, pp 26–29
F.P. Preparata and M.I. Shamos, Computational Geometry — An Introduction, Springer-Verlag, New York, 1985
T. Roos, Voronoi Diagramme, Diplomarbeit, Universität Würzburg, 1988
T. Roos, k — Nearest — Neighbor Voronoi Diagrams for Sets of Convex Polygons, Line Segments and Points, Proceedings 15th Intern. Workshop on Graph-Theoretic Concepts in Computer Science WG89, LNCS 411, Springer-Verlag, Berlin-Heidelberg-New York
T. Roos, Voronoi Diagrams over Dynamic Scenes (Extended Abstract), Proceedings 2nd Canadian Conference on Computational Geometry, Ottawa, 1990
T. Roos, Voronoi Diagrams over Dynamic Scenes, to appear in Discrete Applied Mathematics, 1991
T. Roos and H. Noltemeier, Dynamic Voronoi Diagrams in Motion Planning, to appear on 15th IFIP Conference on System Modeling and Optimization, Zurich, 1991
M.I. Shamos and D. Hoey, Closest — Point Problems, Proc. 16th Annual Symp. on FOCS, 1975, pp 151–162
M. Sharir, Davenport-Schinzel Sequences and their Geometric Applications, pp 253–278, NATO ASI Series, Vol. F40, Theoretical Foundations of Computer Graphics and CAD, R.A. Earnshaw (Ed.), Springer-Verlag Berlin Heidelberg, 1988
K. Sugihara and M. Iri, Construction of the Voronoi Diagram for One Million Generators in Single-Precision Arithmetic, private communications, 1989, to appear in Proc. of IEEE
C.K. Yap, An O(n log n) Algorithm for theVoronoi Diagram of a Set of Simple Curve Segments, Discrete & Computational Geometry, 1987, Vol. 2, pp 365–393
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Guibas, L.J., Mitchell, J.S.B., Roos, T. (1992). Voronoi diagrams of moving points in the plane. In: Schmidt, G., Berghammer, R. (eds) Graph-Theoretic Concepts in Computer Science. WG 1991. Lecture Notes in Computer Science, vol 570. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55121-2_11
Download citation
DOI: https://doi.org/10.1007/3-540-55121-2_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55121-8
Online ISBN: 978-3-540-46735-9
eBook Packages: Springer Book Archive