An optimal parallel algorithm for linear programming in the plane

DOI10.1016/0020-0190(90)90026-TzbMath0702.68057OpenAlexW1999230788MaRDI QIDQ915450

Xiaotie Deng

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90026-t

zbMATH Keywords

parallel algorithmcomputational geometryCRCW PRAM

Mathematics Subject Classification ID

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

Related Items

A PARALLEL ALGORITHM FOR FIXED-DIMENSIONAL LINEAR PROGRAMMING∗, Optimal, output-sensitive algorithms for constructing planar hulls in parallel, Fast randomized parallel methods for planar convex hull construction, Two-variable linear programming in parallel, Two-variable linear programming in parallel

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimally efficient selection algorithm
• Parallel computational geometry
• Finding the intersection of two convex polyhedra
• Finding the intersection of n half-spaces in time O(n log n)
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• The Ultimate Planar Convex Hull Algorithm?
• Finding the maximum, merging, and sorting in a parallel computation model
• The Parallel Evaluation of General Arithmetic Expressions