EFFICIENT GEOMETRIC ALGORITHMS ON THE EREW PRAM

We present a technique that can be used to obtain efficient parallel g eometric algorithms in the EREW PRAM computational model. This techniq ue enables us to solve optimally a number of geometric problems in O(l og n) time using O(n/log n) EREW PRAM processors, where n is the input size of a problem. These problems include: computing the convex hull of a set of points in the plane that are given sorted, computing the c onvex hull of a simple polygon, computing the common intersection of h alf-planes whose slopes are given sorted, finding the kernel of a simp le polygon, triangulating a set of points in the plane that are given sorted, triangulating monotone polygons and star-shaped polygons, and computing the all dominating neighbors of a sequence of values. PRAM a lgorithms for these problems were previously known to be optimal (i.e. , in O(log n) time and using O(n/log n) processors) only on the CREW P RAM, which is a stronger model than the EREW PRAM.