Quentin F. Stout
University of Michigan
Abstract: Given an N x N array of 0s and 1s, the closest pair problem is to determine the minimum distance between any pair of 1s. Let D be this minimum distance (or D=2N if there are fewer than two 1s), where the distance is measured by the L_{1} (taxicab) or L_{∞} metric. Two solutions to this problem are given, one requiring Θ(D+log N) time and the other Θ(log N). These solutions are for two types of parallel computers arranged in a pyramid fashion with the base of the pyramid containing the matrix. These models, pyramid cellular automata, are quite weak in that each processor is a finite automaton which is incapable of holding the answer. These results improve upon an algorithm of Dyer that requires Θ(N) time on a more powerful computer. In particular, the second solution is optimal for any pyramid computer, no matter how powerful the processors.
Keywords: parallel computing, pyramid cellular automata, pyramid computers, closest pair, computational geometry, nearest neighbors, parallel algorithms, finite automaton
Complete paper. This paper appears in J. of Algorithms 6 (1985), pp. 200-212.
My related work in parallel computing
Copyright © 2005-2016 Quentin F. Stout. |