Header menu link for other important links
Randomized algorithms for binary search and load balancing on fixed connection networks with geometric applications
John Reif H.,
Published in Publ by ACM, New York, NY, United States
Pages: 327 - 337
There are now a number of fundamental problems in computational geometry that have optimal algorithms on PRAM models. We present randomized parallel algorithms which execute on an n-processor butterfly inter-connection network in O(log n) time for the following problems of input size n: trapezoidal decomposition, visibility, triangulation and 2-D convex hull. These are based on some previous work of the authors on PRAM algorithms and a new algorithm for doing binary search on fixed connection network. Apart from a 2-D convex hull algorithm, these are the first non-trivial geometric algorithms which attain this performance on fixed connection networks. The techniques developed in this paper rely on random sampling methods to do load-balancing on fixed-connection networks; it seems likely that they will have wider applications.
About the journal
Published in Publ by ACM, New York, NY, United States
Open Access
Impact factor