Coarse Grained Parallel Geometric Search.

A. Chan, F. Dehne, and A. Rau-Chaplin

Abstract: We present a parallel algorithm for solving the next element search problem on a set of line segments, using a BSP like model referred to as the Coarse Grained Multicomputer (CGM). 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) \log p)$ memory per processor, assuming $n/p \geq p$. Our result implies solutions to the point location, trapezoidal decomposition and polygon triangulation problems. A simplified version for axis parallel segments requires only $O(n/p)$ memory per processor, and we discuss an implementation of this version. As in a previous paper by Devillers and Fabri, our algorithm is based on a distributed implementation of segment trees which are of size $O(n \log n)$. This paper improves on Devillers and Fabri results's in several ways: (1) It studies the more general next element search problem which also solves, e.g., planar point location. (2) The algorithms require only $O((n/p) \log n)$ local computation instead of $O(\log p * (n/p) \log n)$. (3) The algorithms require only $O((n/p) \log p)$ local memory instead of $O((n/p) \log n)$.