Optimal randomized parallel algorithms for computational geometry

DOI10.1007/BF01758753zbMath0764.68177OpenAlexW1963700323MaRDI QIDQ1187202

Sandeep Sen, John H. Reif

Publication date: 28 June 1992

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01758753

zbMATH Keywords

triangulationCREW PRAMrandomizedtrapezoidal decompositionplanar-point locationthree-dimensional maximatwo-set dominance counting

Mathematics Subject Classification ID

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

Related Items (4)

Point location among hyperplanes and unidirectional ray-shooting ⋮ Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems ⋮ Dynamic point location in arrangements of hyperplanes ⋮ Applications of random sampling in computational geometry. II

Cites Work

• Unnamed Item
• On parallel integer sorting
• Sorting in \(c \log n\) parallel steps
• Routing, merging, and sorting on parallel models of computation
• \(\epsilon\)-nets and simplex range queries
• Parallel algorithms for some functions of two convex polygons
• New applications of random sampling in computational geometry
• Optimal Point Location in a Monotone Subdivision
• Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
• A Scheme for Fast Parallel Communication
• Parallelism in Comparison Problems
• Multidimensional Searching Problems
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: Optimal randomized parallel algorithms for computational geometry