Randomized algorithms for binary search and load balancing on fixed connection networks with geometric applications


Journal Article

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.

Duke Authors

Cited Authors

  • Reif, JH; Sen, S

Published Date

  • December 1, 1990

Published In

  • Algorithms and Architectures

Start / End Page

  • 327 - 337

Citation Source

  • Scopus