Lower bounds for parallel algebraic decision trees, complexity of convex hulls and related problems

Abstract

We show that any parallel algorithm in the fixed degree algebraic decision tree model that answers membership queries in W R ⁿ using p processors, requires Ω (|W|/n log(p/n)) rounds where |W| is the number of connected components of W. We further prove a similar result for the average case complexity. We give applications of this result to various fundamental problems in computational geometry like convex-hull construction and trapezoidal decomposition and also present algorithms with matching upper bounds.