F. Dehne, A. Chan, and A. Rau-Chaplin, "Coarse Grained Parallel Geometric Search".


We present a parallel algorithm for solving the {\em next element search problem} on a set of line segments, using a BSP like model referred to as the {\em 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)$ storage per processor. 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)$ storage per processor, and we discuss an implementation of this version. As in a previous paper by Develliers and Fabri \cite{star}, our algorithm is based on a distributed implementation of segment trees which are of size $O(n \log n)$. This paper improves on \cite{star} which presented a CGM algorithm for the special case of trapzoidal decomposition only and required $O(\log p * (n/p) \log n)$ local computation.
Keywords: BSP, Coarse Grained Multicomputer, Next Element Search, Planar Subdivision Search, Scalable Parallel Algorithms, Segment Tree, Simple Polygon Triangulation, Trapezoidal Map.

Download Postscript

Home* Publications