About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
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.
Related
Conference paper
Initial agebra sematics
Conference paper