Superlinear Bounds for Matrix Searching Problems

Matrix searching in classes of totally monotone partial matrices has many applications in computer science, operations research, and other areas. This paper gives the first superlinear bound for matrix searching in classes of totally monotone partial matrices, and also contains some new upper bounds for a class with applications in computational geometry and dynamic programming. The precise results of this paper are as follows. We show that any algorithm for finding row maxima or minima in totally monotone partial $2n \times n$ matrices with the property that the non-blank entries in each column form a contiguous segment, can be forced to evaluate $\Omega (n \alpha (n))$ entries of the matrix in order to find the row maxima or minima, where $\alpha (n)$ denotes the very slowly growing inverse of Ackermann's function. A similar result is obtained for $n \times 2n$ matrices with contiguous non-blank segments in each row. The lower bounds are proved by introducing the concept of an independence set in a partial matrix and showing that any matrix searching algorithm for these types of partial matrices can be forced to evaluate every element in the independence set. A result involving lower bounds for Davenport-Schinzel sequences is then used to construct an independence set of size $\Omega (n \alpha (n))$ in the matrices of size $2n \times n$ and $n \times 2n$. We also give two algorithms to find row maxima and minima in totally monotone partial $n \times m$ matrices with the property that the non-blank entries in each column form a contiguous segment ending at the bottom row. The first algorithm evaluates at most $O (m \alpha (n) + n)$ entries of the skyline matrix and performs at most that many comparisons, but may have $O (m \alpha (n) \log \log n+ n)$ total running time. The second algorithm is simpler and has $O (m \log \log n+ n)$ total running time. A preliminary version of this paper appeared in the Proceedings of the First ACM/SIAM Symposium on Discrete Algorithms, 1990. The research in this paper was partially supported by an NSERC Operating Grant.