Applications of generalized matrix searching to geometric algorithms

Abstract

This paper introduces a generalization of totally monotone matrices, namely totally monotone partial matrices, shows how a number of problems in computational geometry can be reduced to the problem of finding the row maxima and minima in totally monotone partial matrices, and gives an O((m+nlog logn) algorithm for finding row maxima and minima in an n×m totally monotone partial matrix. In particular, if P and Q are nonintersecting n and m vertex convex polygons, respectively, our methods give an O((m+n)log logn) algorithm for finding for each vertex x of P, the farthest vertex of Q which is not visible to x, and the nearest vertex of Q which is not visible to x. © 1990.