Implementing data structures on a hypercube multiprocessor, and applications in parallel computational geometry
In this paper, we study the problem of implementing standard data structures on a hypercube multiprocessor. We present a technique for efficiently executing multiple independent 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 obtaining O(long2n) time algorithms for solving the next element search problem, the trapezoidal composition problem, and the triangulation problem.
|Journal||Journal of Parallel and Distributed Computing|
Dehne, F, & Rau-Chaplin, A. (Andrew). (1990). Implementing data structures on a hypercube multiprocessor, and applications in parallel computational geometry. Journal of Parallel and Distributed Computing, 8(4), 367–375. doi:10.1016/0743-7315(90)90135-C