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. This paper presents randomized parallel algorithms that execute on an n-processor butterfly interconnection network in O(log n) time for the following problems of input size n: trapezoidal decomposition, visibility, triangulation, and two-dimensional convex hull. These algorithms involve tackling some of the very basic problems, like binary search and load balancing, that are taken for granted in PRAM models. Apart from a two-dimensional convex hull algorithm, these are the first nontrivial geometric algorithms that attain this performance on fixed connection networks. These techniques use a number of ideas from Flashsort that have to be modified to handle more difficult situations; it seems likely that they will have wider applications.

Full Text

Duke Authors

Cited Authors

  • Reif, JH; Sen, S

Published Date

  • January 1, 1994

Published In

Volume / Issue

  • 23 / 3

Start / End Page

  • 633 - 651

International Standard Serial Number (ISSN)

  • 0097-5397

Digital Object Identifier (DOI)

  • 10.1137/S0097539790184298

Citation Source

  • Scopus