Efficient BSR-Based Parallel Algorithms for Geometrical Problems

This paper presents BSR-parallel algorithms for three geometrical problems: point location, convex hull and smallest enclosing rectangle. These problems are solved in constant time using the BSR model introduced by S. Akl in (21. The first algorithm uses O ( N) processors ( N is the number of edges of the polygon R). The second uses O ( N " ) processors (N ' is the nuniber of points) and the third one uses O(N") processors (it need the convex hull} to solve the smallest enclosing rectangle problem. These new results suggest that many other geometrical problenzs can be solved in constant time using the BSR model. 1