Header menu link for other important links
Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems
Published in Elsevier
Volume: 188
Issue: 1-2
Pages: 59 - 78
We present lower bounds on the number of rounds required to solve a decision problem in the parallel algebraic decision tree model. More specifically, we show that any parallel algorithm in the fixed degree algebraic decision tree model that answers membership queries in W ⊆ Rn using p processors, requires Ω(log |W|/n log(p/n)) rounds where |W| is the number of connected components of W. This implies non-trivial lower bounds for parallel algorithms that use a superlinear number of processors, namely, that the speed-up obtainable in such cases is not proportional to the number of processors. 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. The algorithms extend Reif and Sen's work in parallel computational geometry to the sublogarithmic time range based on recent progress in padded-sorting. A corollary of our result strengthens the known lower-bound of parallel sorting from the parallel comparison tree model to the more powerful bounded-degree decision tree.
About the journal
Published in Elsevier
Open Access
Impact factor