Optimal parallel algorithms for computing convex hulls and for sorting

DOI10.1007/BF02243071zbMath0526.68062OpenAlexW1572664488MaRDI QIDQ594601

Selim G. Akl

Publication date: 1984

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02243071

zbMATH Keywords

selectionmedianconvex hullparallel algorithmparallel sorting algorithm

Mathematics Subject Classification ID

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