Applications of generalized matrix searching to geometric algorithms (Q913505): Difference between revisions

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+n)\log \log n)\) algorithm for finding row maxima and minima in an \(n\times 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 \log n)\) 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.