Dynamic Computational Geometry on Meshes and Hypercubes.
Laurence Boxer, Russell B. Miller · Proceedings of the International Conference on Parallel Processing · 1988
Parallel algorithms are given for determining geometric properties of systems of moving point-objects. The objects are assumed to be moving in a Euclidean space such that each coordinate of a point's motion is a polynomial of bounded degree in the time variable. The properties investigated include nearest (farthest) neighbor, closest (farthest) pair, collision, convex hull, diameter, and containment. Several of these properties are investigated from both the dynamic and steady-state points of view. Efficient, and often optimal, implementations of these algorithms are given for the mesh and hypercube.