An Almost Linear Time Algorithm for Generalized Matrix Searching

An O( mα ( n ) + n ) time algorithm is given for finding row-maxima and minima in totally monotone partial n × 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 α ( 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.