Maintaining Voronoi diagrams in parallel

We are given a set of n points moving continuously along given trajectories in d-dimensional Euclidean space. At each instant, these sites define a Voronoi diagram which changes continuously over time except of certain critical instances, so-called topological events. We present an algorithm for maintaining the Voronoi diagram in parallel over time using only O(1) time per event on a CREW PRAM with O/spl lsqb/n/sup d/2spl rsqb/ processors which is worst-case optimal. This work generalizes the most recent single processor algorithms to PRAMs. Additionally, the presented technique provides the first efficient algorithm for computing static higher dimensional Voronoi diagrams in parallel. Finally, we present a new upper bound on the number of topological events which may appear during the flow of the sites. This result tightens a long-open gap between the upper and lower worst-case bounds, actually providing matching bounds in some cases, and is interesting in its own right.<>