Parallel fractional cascading on hypercube multiprocessors

Dehne, F., A. Ferreira and A. Rau-Chaplin, Parallel fractional cascading on hypercube multiprocessors, Computational Geometry: Theory and Applications 2 (1992) 141-167. In this paper we present a new data-structuring technique for parallel computational geometry on a hypercube multiprocessor. This technique, called hypercube cascading, is an efficient parallel implementation of fractional cascading for the hypercube multiprocessor. That is, it allows complex data structures with catalogs to be traversed efficiently in parallel by a large number of simultaneous queries. We show that for monotone graphs with n nodes, m multiple look-up queries with path length at most p (including catalog look-ups) can be executed independently, in parallel, in time O(p log N + ts(N)) on a hypercube multiprocessor of size N = maxn, itm. The term ts(N) denotes the time for sorting N elements on a hypercube of size N; currently ts(N) = O(log N log log N). Note that, the best known sequential time complexity for one multiple look-up query, as presented by Chazelle and Guibas, is O(p + log N). Our solution allows an arbitrary number of search queries to access the same node and its catalog at the same time. We present two parallel computational geometry applications of this technique: multiple stabbing of a simple polygonal path and multiple slanted range search