A sublogarithmic convex hull algorithm

DOI10.1007/BF01931655zbMath0696.68056OpenAlexW1986754491MaRDI QIDQ911280

Per-Olof Fjällström, Christos Levcopoulos, Ola Petersson, Jyrki Katajainen

Publication date: 1990

Published in: BIT (Search for Journal in Brave)

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

zbMATH Keywords

parallel algorithmcomputational geometrydivide-and-conquerconvex hull problemCRCW PRAM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Variants of convex sets (star-shaped, ((m, n))-convex, etc.) (52A30)

Related Items

An optimal parallel algorithm for the Euclidean distance maps of 2-D binary images ⋮ CONSTRUCTING A STRONGLY CONVEX SUPERHULL OF POINTS ⋮ Finding the Convex Hull of Discs in Parallel

Cites Work

• Unnamed Item
• Parallel algorithms for some functions of two convex polygons
• Finding the convex hull of a sorted point set in parallel
• Parallel computational geometry
• Optimal parallel algorithms for point-set and polygon problems
• Faster optimal parallel prefix sums and list ranking
• An efficient algorithm for determining the convex hull of a finite planar set
• Finding the maximum, merging, and sorting in a parallel computation model
• Optimal bounds for decision problems on the CRCW PRAM