Parallel Algorithms for Grounded Range Search and Applications. 

M. Lamoureux and A. RauChaplin 

Abstract: This paper presents a parallel algorithm for solving grounded range search in associativefunction mode using the BSPlike Coarse Grained Multicomputer (CGM). Given a set $S$ of $n$ weighted points in the plane, the algorithm requires $O(1)$ communication rounds (hrelations with $h = O(n/p))$, $O((n/p)\log n)$ local computation, and $O(n/p)$ memory per processor ($n/p \geq p$), to solve $m=O(n)$ grounded range search problems. % The result implies new or improved solutions to a number of other geometric applications including ddimensional range search, quadrant search, interval intersection, and chromatic range queries. 

paper.pdf 
paper.ps 

