Header menu link for other important links
Lower bounds for parallel algebraic decision trees, complexity of convex hulls and related problems
Published in Springer Verlag
Volume: 880 LNCS
Pages: 193 - 204
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 Ω (|W|/nlog(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. © 1994, Springer Verlag. All rights reserved.
About the journal
Published in Springer Verlag
Open Access
Impact factor