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

DOI10.1137/0221031MaRDI QIDQ4016909zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

convex-hullsparallel algorithmsrandomization

Mathematics Subject Classification ID

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

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

Cited in

(25)

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

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)