PARALLEL ALGORITHMS FOR DYNAMIC SYSTEMS WITH KNOWN TRAJECTORIES.

Parallel algorithms are given for determining geometric properties of systems of moving objects. The properties investigated include nearest (farthest) neighbor, closest (farthest) pair, collision, convex hull, and containment. Several of these properties are investigated from both the dynamic and steady-state points of view. Typical running times of the algorithms are O(log**2n) for dynamic problems and O(log n) to O(log n log log n) for steady-state problems. The model of computation is that of a concurrent-read-exclusive-write parallel random-access machine.