Optimal randomized parallel algorithms for computational geometry

DOI10.1007/BF01758753zbMath0764.68177MaRDI QIDQ1187202

Sandeep Sen, John H. Reif

Publication date: 28 June 1992

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

triangulation; CREW PRAM; randomized; trapezoidal decomposition; planar-point location; three-dimensional maxima; two-set dominance counting

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68W15: Distributed algorithms

Related Items

Dynamic point location in arrangements of hyperplanes, Point location among hyperplanes and unidirectional ray-shooting, Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems, 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