ML Anthology

Convexity Algorithms for Parallel Machines

Russ Miller, Quentin F. Stout
CVPR 1988 pp. 918-924
doi:10.1109/CVPR.1988.196342 /cvpr/1988/miller1988cvpr-convexity/

Abstract

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 Theta (n) processors, the authors introduce a worst-case hypercube algorithm that finishes in Theta (log n) time, a worst-case algorithm for the pyramid, tree, and mesh-of-trees that finishes in Theta (log/sup 3/ n/log logn)-time, and a worst-case algorithm for the mesh with reconfigurable bus that finishes in Theta (log/sup 2/ 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 Theta (log n) time hypercube 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 random fashion one point per processor.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

CVPR Semantic Scholar

Cite

Text

Miller and Stout. "Convexity Algorithms for Parallel Machines." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 1988. doi:10.1109/CVPR.1988.196342

Markdown

[Miller and Stout. "Convexity Algorithms for Parallel Machines." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 1988.](https://mlanthology.org/cvpr/1988/miller1988cvpr-convexity/) doi:10.1109/CVPR.1988.196342

BibTeX

@inproceedings{miller1988cvpr-convexity,
  title     = {{Convexity Algorithms for Parallel Machines}},
  author    = {Miller, Russ and Stout, Quentin F.},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year      = {1988},
  pages     = {918-924},
  doi       = {10.1109/CVPR.1988.196342},
  url       = {https://mlanthology.org/cvpr/1988/miller1988cvpr-convexity/}
}