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. 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.

Duke Scholars

Author John H. Reif Computer Science