Publications [#236931] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH; Sen, S, Randomized algorithms for binary search and load balancing on fixed connection networks with geometric applications, Algorithms and Architectures (December, 1990), pp. 327-337 [pdf]
   (last updated on 2026/01/14)

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