Fast randomized parallel methods for planar convex hull construction

DOI10.1016/0925-7721(95)00036-4MaRDI QIDQ676065zbMATH OpenOpenAlexFDO

Authors Mujtaba R. Ghouse, Michael T. Goodrich

Publication date 4 January 1998

Published in Computational Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/0925-7721(95)00036-4

zbMATH Keywords

parallel algorithmsfailure sweeping

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distributed algorithms (68W15)

Recommendations

• A FAST PARALLEL ALGORITHM FOR FINDING THE CONVEX HULL OF A SORTED POINT SET
• Optimal, output-sensitive algorithms for constructing planar hulls in parallel
• Finding the convex hull of a sorted point set in parallel
• A sublogarithmic convex hull algorithm

Cites work

• scientific article; zbMATH DE number 1003255 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 177853 (Why is no real title available?)
• scientific article; zbMATH DE number 589497 (Why is no real title available?)
• A FAST PARALLEL ALGORITHM FOR FINDING THE CONVEX HULL OF A SORTED POINT SET
• A Lower Bound to Finding Convex Hulls
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A guided tour of Chernoff bounds
• An efficient algorithm for determining the convex hull of a finite planar set
• An optimal parallel algorithm for linear programming in the plane
• Constructing the convex hull of a partially sorted set of points
• Derandomizing an output-sensitive convex hull algorithm in three dimensions
• Efficient parallel convex hull algorithms
• Finding an approximate median with high probability in constant parallel time
• Finding the convex hull of a sorted point set in parallel
• Optimal merging and sorting on the EREW PRAM
• Parallel algorithms for some functions of two convex polygons
• Parallel computational geometry
• The Ultimate Planar Convex Hull Algorithm?

Cited in

(11)

• Finding the convex hull of a sorted point set in parallel
• Comments on two parallel algorithms for the planar convex hull problem
• Computational Science and Its Applications – ICCSA 2004
• Optimal randomized parallel algorithms for computational geometry
• Faster output-sensitive parallel algorithms for 3D convex hulls and vector maxima.
• Finding the Convex Hull of Discs in Parallel
• On a Simple, Practical, Optimal, Output-Sensitive Randomized Planar Convex Hull Algorithm
• Efficient parallel convex hull algorithms
• Robust algorithms for constructing strongly convex hulls in parallel.
• Synergistic solutions for merging and computing planar convex hulls
• Locating two obnoxious facilities using the weighted maximin criterion

This page was built for publication: Fast randomized parallel methods for planar convex hull construction

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