Pyramid Computer Parallel Algorithms To Find the Closest Pair of Points

Pyramid Computer Solutions of the Closest Pair Problem

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

My papers in parallel computing and an overview of my research.
An explanation of parallel computing, a tutorial, Parallel Computing 101, and a list of parallel computing resources.
Our book, R Miller and QF Stout, Parallel Algorithms for Regular Architectures: Meshes and Pyramids, MIT Press, 1996, that contains many algorithms for pyramid computers.