Randomized algorithms for binary search and load balancing on fixed connection networks with geometric applications
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.
