A sublogarithmic convex hull algorithm

DOI10.1007/BF01931655MaRDI QIDQ911280zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• An approximate algorithm for computing multidimensional convex hulls
• An optimal convex hull algorithm in any fixed dimension
• A fast approximation to a convex hull
• Sublinear Geometric Algorithms
• Sublinear geometric algorithms
• The quickhull algorithm for convex hulls
• A characterization theorem and an algorithm for a convex hull problem
• Exact and approximate map-reduce algorithms for convex hull
• scientific article; zbMATH DE number 828002

Cites work

• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• An efficient algorithm for determining the convex hull of a finite planar set
• Faster optimal parallel prefix sums and list ranking
• Finding the convex hull of a sorted point set in parallel
• Finding the maximum, merging, and sorting in a parallel computation model
• Optimal bounds for decision problems on the CRCW PRAM
• Optimal parallel algorithms for point-set and polygon problems
• Parallel algorithms for some functions of two convex polygons
• Parallel computational geometry

Cited in

(18)

• A BSP realisation of Jarvis' algorithm
• Finding the convex hull of a sorted point set in parallel
• scientific article; zbMATH DE number 3945382 (Why is no real title available?)
• New serial and parallel algorithms for finding convex hull based on clusters, domains and directions from single to multitude
• Incremental algorithms for finding the convex hulls of circles and the lower envelopes of parabolas
• An optimal parallel algorithm for the Euclidean distance maps of 2-D binary images
• Finding the Convex Hull of Discs in Parallel
• CONSTRUCTING A STRONGLY CONVEX SUPERHULL OF POINTS
• Efficient parallel convex hull algorithms
• THE PARALLEL 3D CONVEX HULL PROBLEM REVISITED
• A 1 log N parallel algorithm for detecting convex hulls on image boards
• A 2-D parallel convex hull algorithm with optimal communication phases
• On the complexity of convex hull algorithms if rotational minima can be found very fast
• Constructing the convex hull of a partially sorted set of points
• Robust algorithms for constructing strongly convex hulls in parallel.
• Fast randomized parallel methods for planar convex hull construction
• Parallel construction of subdivision hierarchies
• scientific article; zbMATH DE number 4062600 (Why is no real title available?)

This page was built for publication: A sublogarithmic convex hull algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911280)