Publications [#237109] 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, SIAM Journal on Computing, vol. 23 no. 3 (January, 1994), pp. 633-651, Society for Industrial & Applied Mathematics (SIAM) [doi]
   (last updated on 2026/02/08)

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