Fast randomized parallel methods for planar convex hull construction

DOI10.1016/0925-7721(95)00036-4zbMATH Open0878.68126OpenAlexW2018318565MaRDI QIDQ676065FDOQ676065

Authors: Mujtaba R. Ghouse, Michael T. Goodrich 

Publication date: 4 January 1998

Published in: Computational Geometry (Search for Journal in Brave)

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

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

zbMATH Keywords

parallel algorithmsfailure sweeping

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

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

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)