TY - GEN
T1 - Convexity algorithms for parallel machines.
AU - Miller, R.
AU - Stout, Q. F.
PY - 1988
Y1 - 1988
N2 - The authors present a parallel algorithms to identify (i.e., detect and enumerate) the extreme points of the convex hull of a set of planar points using a hypercube, pyramid, tree, mesh-of-trees, mesh with reconfigurable bus, EREW PRAM (exclusive read, exclusive write parallel random-access machine) and AKS sorting network. For the situation where the input set of n planar points is given ordered one per processor on a machine with Θ(n) processors, the authors introduce a worst-case hypercube algorithm that finishes in Θ(log n) time, a worst-case algorithm for the pyramid, tree, and mesh-of-trees that finishes in Θ(log3 n/log log n)-time, and a worst-case algorithm for the mesh with reconfigurable bus that finishes in Θ(log2 n) time. For the situation where the input set is given unordered one per processor, several optimal worst-case algorithms are given. It is shown that the Θ(log n) time hypercube algorithm algorithm for ordered data will extend to yield a worst-case optimal EREW PRAM algorithm and AKS sorting network algorithm for the case where the set of planar points is distributed in a random fashion one point per processor.
AB - The authors present a parallel algorithms to identify (i.e., detect and enumerate) the extreme points of the convex hull of a set of planar points using a hypercube, pyramid, tree, mesh-of-trees, mesh with reconfigurable bus, EREW PRAM (exclusive read, exclusive write parallel random-access machine) and AKS sorting network. For the situation where the input set of n planar points is given ordered one per processor on a machine with Θ(n) processors, the authors introduce a worst-case hypercube algorithm that finishes in Θ(log n) time, a worst-case algorithm for the pyramid, tree, and mesh-of-trees that finishes in Θ(log3 n/log log n)-time, and a worst-case algorithm for the mesh with reconfigurable bus that finishes in Θ(log2 n) time. For the situation where the input set is given unordered one per processor, several optimal worst-case algorithms are given. It is shown that the Θ(log n) time hypercube algorithm algorithm for ordered data will extend to yield a worst-case optimal EREW PRAM algorithm and AKS sorting network algorithm for the case where the set of planar points is distributed in a random fashion one point per processor.
UR - https://www.scopus.com/pages/publications/0024142192
M3 - Conference contribution
AN - SCOPUS:0024142192
SN - 0818608625
T3 - Proc CVPR 88 Comput Soc Conf on Comput Vision and Pattern Recognit
SP - 918
EP - 924
BT - Proc CVPR 88 Comput Soc Conf on Comput Vision and Pattern Recognit
PB - Publ by IEEE
ER -