We defne the batched range-searching 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, computer-aided design and engineering. We present several parallel algorithms for this problem on coarse-grained multicomputers. Our algorithms are based on well-known average- and worst-case effcient sequential algorithms. One of our algorithms solves the d-dimensional batched range-searching problem in O(T_s(n log^d-1p,p) + T_s(m log^d-1p,p) + ((m +n)log^d-1(n/p) + m log^d-1p log(n/p) + k)/p) time on a p-processor coarse-grained multicomputer. (T_s(n,p) denotes the time globally to sort n numbers on a p-processor 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.