Optimal parallel algorithms for computing convex hulls and for sorting
From MaRDI portal
Publication:594601
DOI10.1007/BF02243071zbMath0526.68062OpenAlexW1572664488MaRDI QIDQ594601
Publication date: 1984
Published in: Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02243071
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Convex sets in (2) dimensions (including convex curves) (52A10) Discrete mathematics in relation to computer science (68R99)
Related Items (16)
Permutation algorithms on optical multi-trees ⋮ Optimal, output-sensitive algorithms for constructing planar hulls in parallel ⋮ Constant time sorting on a processor array with a reconfigurable bus system ⋮ On the complexity of min-max sorting networks ⋮ Data-movement-intensive problems: Two folk theorems in parallel computation revisited ⋮ Optimal parallel selection in sorted matrices ⋮ Perfectly overlapped merging and sorting on a two-way linear array ⋮ Improved fault-tolerance sorting algorithm in hypercubes ⋮ Unnamed Item ⋮ On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs ⋮ A unified algorithm for sorting on multidimensional mesh-connected processors ⋮ A generalization of the zero-one principle for sorting algorithms ⋮ Parallel algorithms for merging and sorting ⋮ From Parallelism to Nonuniversality: An Unconventional Trajectory ⋮ Sorting and computing convex hulls on processor arrays with reconfigurable bus systems ⋮ An Output-Sensitive Convex Hull Algorithm for Planar Objects
Cites Work
- Unnamed Item
- Unnamed Item
- Routing, merging, and sorting on parallel models of computation
- A constant-time parallel algorithm for computing convex hulls
- A fast convex hull algorithm
- An efficient algorithm for determining the convex hull of a finite planar set
- The Ultimate Planar Convex Hull Algorithm?
- Finding the maximum, merging, and sorting in a parallel computation model
- A Lower Bound to Finding Convex Hulls
- Parallel permutation and sorting algorithms and a new generalized connection network
- Convex hulls of finite sets of points in two and three dimensions
- New Parallel-Sorting Schemes
- Algorithm and Hardware for a Merge Sort Using Multiple Processors
- Parallel Processing with the Perfect Shuffle
This page was built for publication: Optimal parallel algorithms for computing convex hulls and for sorting