An Almost Linear Time Algorithm for Generalized Matrix Searching

Abstract

An $O( m\alpha ( n ) + n )$ time algorithm is given for finding row-maxima and minima in totally monotone partial $n \times n$ matrices. As a result, faster algorithms are obtained for some optimization problems concerning distance and visibility between vertices of two convex polygons. Also shown is how the algorithm can be modified to give an $O( n \alpha ( n ) )$ algorithm for a class of dynamic programming problems satisfying convex quadrangle inequalities. This results in faster algorithms for a number of problems arising in molecular biology, speech recognition, and geology.