Parallel fractional cascading on hypercube multiprocessors

作     者：Dehne, F. Ferreira, A. Rau-Chaplin, A. 

作者机构：Center for Parallel and Distributed Computing School of Computer Science Carleton University Ottawa Canada K1S 5B6 CNRS-Laboratoire de l'Informatique du Parallelisme Ecole Normale Superieure de Lyon 69364 Lyon cedex 07 France 

出 版 物：《Computational Geometry: Theory and Applications》 (Comput Geom Theory Appl)

年 卷 期：1992年第2卷第3期

页      面：141-141页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Natural Sciences and Engineering Research Council of Canada  NSERC 

摘      要：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 + t s ( N )) on a hypercube multiprocessor of size N = max n, itm . The term t s ( N ) denotes the time for sorting N elements on a hypercube of size N ; currently t s ( 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.