An efficient algorithm for row minima computations on basic reconfigurable meshes

A matrix A of size m×n containing items from a totally ordered universe is termed monotone if, for every i, j, 1⩽i<j⩽m, the minimum value in row j lies below or to the right of the minimum in row i monotone matrices, and variations thereof, are known to have many important applications. In particular, the problem of computing the row minima of a monotone matrix is of import in image processing, pattern recognition, text editing, facility location, optimization, and VLSI. Our first main contribution is to exhibit a number of nontrivial lower bounds for matrix search problems. These lower bound results hold for arbitrary, infinite, two-dimensional reconfigurable meshes as long as the input is pretiled onto a contiguous n×n submesh thereof. Specifically in this context, we show that every algorithm that solves the problem of computing the minimum of an n×n matrix must take Ω(log log n) time. The same lower bound is shown to hold for the problem of computing the minimum in each row of an arbitrary n×n matrix. As a by product, we obtain an Ω(log log n) time lower bound for the problem of selecting the kth smallest item in a monotone matrix, thus extending the best previously known lower bound for selection on the reconfigurable mesh. Finally, we show an Ω(√loglogn) time lower bound for the task of computing the row minima of a monotone n×n matrix. Our second main contribution is to provide a nearly optimal algorithm for the row-minima problem: With a monotone matrix of size m×n with m⩽n pretiled, one item per processor, onto a basic reconfigurable mesh of the same size, our row-minima algorithm runs in O(log n) time if 1⩽m⩽2 and in O(logn/logm loglog m) time if m>2. In case m=n^ε for some constant ε, (0<ε⩽1), our algorithm runs in O(log log n) time