Publication
FOCS 1987
Conference paper

Notes on searching in multidimensional monotone arrays

View publication

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.

Date

Publication

FOCS 1987

Authors

Share