Implementing data structures on a hypercube multiprocessor, and applications in parallel computational geometry

Abstract, In this paper, we study the problem of implementing standard data structures on a hypercube multiprocessor. We present a technique for fficiently executing multiple independant search processes on a class of graphs called ordered h-level graphs. We show how this technique can be utilized to implement a segment tree on a hypercube, thereby obtainig O(logZn) time algorithms for sotving the next element search problem, the trapezoidal decomposition probtem, the triangulation problem, and the (multiple) planar point location problem.