Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems

DOI10.1137/0221031zbMATH Open0761.68100OpenAlexW4238964467MaRDI QIDQ4016909FDOQ4016909

Authors: J. Reif, Sandeep Sen 

Publication date: 16 January 1993

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0221031

Recommendations

• A randomized parallel three-dimensional convex hull algorithm for coarse-grained multicomputers
• Optimal randomized parallel algorithms for computational geometry
• A time-optimal parallel algorithm for three-dimensional convex hulls
• Optimal parallel randomized algorithms for the Voronoi diagram of line segments in the plane
• New parallel algorithms for convex hull and triangulation in 3-dimensional space

zbMATH Keywords

randomizationparallel algorithmsconvex-hulls

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (21)

• Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems
• New parallel algorithms for convex hull and triangulation in 3-dimensional space
• Optimal randomized parallel algorithms for computational geometry
• Derandomizing an output-sensitive convex hull algorithm in three dimensions
• Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
• Computational Science and Its Applications – ICCSA 2004
• On a Simple, Practical, Optimal, Output-Sensitive Randomized Planar Convex Hull Algorithm
• A nearly optimal deterministic parallel Voronoi diagram algorithm
• Title not available (Why is that?)
• An optimal convex hull algorithm in any fixed dimension
• THE PARALLEL 3D CONVEX HULL PROBLEM REVISITED
• Erratum: Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems
• A time-optimal parallel algorithm for three-dimensional convex hulls
• Title not available (Why is that?)
• Parallelism in randomized incremental algorithms
• Optimal, output-sensitive algorithms for constructing planar hulls in parallel
• Sigma-local graphs
• RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
• Title not available (Why is that?)
• RANDOMIZED PARALLEL ALGORITHMS FOR TRAPEZOIDAL DIAGRAMS
• Faster output-sensitive parallel algorithms for 3D convex hulls and vector maxima.

This page was built for publication: Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems

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