Abstract: Given n points chosen uniformly and independently from the unit square, it is shown that a parallel random access machine (PRAM) with n processors can solve several geometric problems in constant expected time. Thus linear speedup is achieved concurrently with achieving the minimal possible time. It appears that these results are the first constant-time geometric results for the PRAM or any other parallel computer model when the number of processors is no larger than the number of points.
Problems solvable in constant expected time include determining for each point whether it is an extreme point of the convex hull, determining for each point whether it is dominated by any other points, determining for each dominated point a maximal point that dominates it, finding the closest pair of points, and finding the furthest pair of points.
These results extend to points chosen uniformly from the unit-cube in d-dimensional space, and to many nonuniform distributions.
The convex hull, domination, and furthest point algorithms involve doing a first step which, which high probability, reduces the data set to a small number of points remaining to be considered. Then the processor to point ratio is very high, and significantly different techniques can be utilized. However, the remaining points must first be moved into a small array so that the processors can locate them and help in the processing. Usually the points would be packed into the initial positions of an array, but that is impossible to accomplish in constant time. Therefore the array is made larger than the expected number of points remaining, and the points are mapped to random locations. The array must be large enough so that this randomized mapping can be accomplished in constant time, yet small enough so that the processor to point ratio remains sufficiently high.
The algorithms also have the property that if a step is reached where something undesired happens, then they resort to a standard worst-case polylogarithmic time algorithm. Since this happens with very small probability, the expected time remains constant.
The PRAM is assumed to be concurrent read concurrent write (CRCW), though only a weak concurrent write is needed. The concurrent write can either be common write, where the only time two or more processors simultaneously write to the same cell they write the same value (which ends up in the cell), or a collision write, whereby if two or more processors simultaneously write to the same memory location then the memory value becomes ``collision'', or several other concurrent write variants. The collision write is also called a ``detecting'' write, and the paper denotes this variation as CRDW.
Keywords: parallel algorithm, random points, computational geometry, CRCW PRAM, optimal algorithm, SIMD, parallel computing, convex hull, domination, maximal point, closest pair, furthest pair
Complete paper. This paper appears in Proc. 1988 International Conference on Parallel Processing, vol. III, pp. 104-107.
Related Work:
|
Copyright © 2005-2018 Quentin F. Stout |