AbstractIn d-dimensional Euclidean space Ed, d > = 2, we are given k < = n points moving continuously along given trajectories and n-k points that stay fixed at their position. At each instant, the points define a Voronoi diagram which changes continuously except for certain critical instants, so-called topological events. We improve the currently known upper worst-case bound on the number of topological events for k in O(sqrt(n)) and provide - for the first time - matching upper and lower worst-case bounds in the case of k being some constant.
Categories and Subject Descriptors: E.1 [Data Structures]; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.1 [Discrete Mathematics]: Combinatorics; I.1.2 [Algebraic Manipulation]: Algorithms; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling
Additional Key Words and Phrases: analysis of algorithms, computational geometry, Delaunay triangulation, kinematic objects, Voronoi diagram
Selected references
- Thomas Roos and Gerhard Albers. Maintaining proximity in higher dimensional spaces. In Ivan M. Havel and Václav Koubek, editors, Mathematical Foundations of Computer Science 1992, 17th International Symposium, volume 629 of Lecture Notes in Computer Science, pages 483-493, Prague, Czechoslovakia, 24-28 August 1992. Springer.