Notes on searching in multidimensional monotone arrays

Abstract

A two-dimensional array A = {ai,j} is called monotone if the maximum entry in its ith row lies below or to the right of the maximum entry in its (i- 1)-st row. An array A is called totally monotone if every 2 × 2 subarray (i.e., every 2 × 2 minor) is monotone. The notion of two-dimensional totally monotone arrays is generalized to multidimensional arrays, and exhibit a wide variety of problems are exhibited involving computational geometry, dynamic programming, VLSI river routing, and finding certain kinds of shortest paths that can be solved efficiently by finding maxima in totally monotone arrays.