Files:  Description  File size  Format  
Fulltext  PDF (requires Acrobat Reader)  
Fulltext  PostScript (requires a PostScript Reader)  
Author:  PerOlof Fjällström  
Article title:  Parallel Algorithms for Batched Range Searching on CoarseGrained Multicomputers  
Publ. type:  Article  
Volume:  2  
Article No:  3  
Language:  English  
Abstract [en]:  We defne the batched rangesearching problem as follows: given a set S of n points and a set Q of m hyperrectangles, report for each hyperrect; angle which points it contains. This problem has applications in, for ex ample, computeraided design and engineering. We present several parallel algorithms for this problem on coarsegrained multicomputers. Our algorithms are based on wellknown average and worstcase effcient sequential algorithms. One of our algorithms solves the ddimensional batched rangesearching problem in O(T_{s}(n log^{d1}p,p) + T_{s}(m log^{d1}p,p) + ((m +n)log^{d1}(n/p) + m log^{d1}p log(n/p) + k)/p) time on a pprocessor coarsegrained multicomputer. (T_{s}(n,p) denotes the time globally to sort n numbers on a pprocessor multicomputer, and k is the total number of reported points. The work presented here is funded by CENIIT (the Center for Industrial Information Technology) at Linkoping University. 

Keywords:  Parallel algorithms, coarse,grained multicomputers, range searching  
Publisher:  Linköping University Electronic Press  
Year:  1997  
Available:  19970401  
No. of pages:  14  
Series:  Linköping Electronic Articles in Computer and Information Science  
ISSN:  14019841  
REFERENCE TO THIS PAGE:
