Parallel Algorithms for Grounded Range Search and Applications.

M. Lamoureux and A. Rau-Chaplin

Abstract: This paper presents a parallel algorithm for solving grounded range search in associative-function mode using the BSP-like Coarse Grained Multicomputer (CGM). Given a set $S$ of $n$ weighted points in the plane, the algorithm requires $O(1)$ communication rounds (h-relations 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 d-dimensional range search, quadrant search, interval intersection, and chromatic range queries.