Nordic Journal of Computing Bibliography

Thomas Roos. New Upper Bounds on Voronoi Diagrams of Moving Points. Nordic Journal of Computing, 4(2):167-171, Summer 1997.
Abstract

In 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


Shortcuts:

  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database