An optimal parallel algorithm for the maximal element problem (abstract)

摘要

Given a set (p1, p2, …, pn) of n points in a plane, a point pi dominates another point pj iff X (pi) ≥ X(pj) and Y (pi) ≥ Y(pj) where X (p) and Y (p) denote the coordinates of a point p. Our problem is to find the points which are dominated by no other point. These points are called maximal elements. In this abstract we suggest an &Ogr; (log n) parallel algorithm with &Ogr; (n) processors in the EREW parallel model which is weaker than CREW. (Note that most parallel algorithms in the literature use the power of CREW PRAM model.) The main idea is to reduce the problem to the parallel prefix problem [2]. Our algorithm runs as follows: First, from P = {pl, …, pn}, find a subset P' = {p1 …, pm }, where each point pi is dominated by no other point having the same X -coordinate aspi. This can be done in &Ogr; (log n) time with &Ogr; (n) processors in the EREW model applying the parallel sort algorithm by [1]. Next sort P' according to the X -coordinate of each point and store each Y -coordinate in an array A in the increasing order of the corresponding X -coordinate. Assume that the Y -coordinate of pi is stored in A [i ] for i = 1, 2, …, m. Then for each A [i ], find an index j such that i ≤ j and A [j] ≥ A [k ] for each i ≤ k ≤ m. If i = j, then pi is one ofthe maximal elements. This can be done in &Ogr; (log n) time with &Ogr; (n) processors on the EREW parallel model by applying a parallel prefix algorithm |2|.