Pyramid Computer Solutions of the Closest Pair Problem

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 L1 (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

Quentin's Home Copyright © 2005-2017 Quentin F. Stout.