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.
Publication
Algorithmica
Paper
Geometric applications of a matrix-searching algorithm
Abstract
Let A be a matrix with real entries and let j(i) be the index of the leftmost column containing the maximum value in row i of A. A is said to be monotone if i 1 >i 2 implies that j(i 1) ≥J(i 2). A is totally monotone if all of its submatrices are monotone. We show that finding the maximum entry in each row of an arbitrary n x m monotone matrix requires Θ(m log n) time, whereas if the matrix is totally monotone the time is Θ(m) when m≥n and is Θ(m(1 + log(n/m))) when m<n. The problem of finding the maximum value within each row of a totally monotone matrix arises in several geometric algorithms such as the all-farthest-neighbors problem for the vertices of a convex polygon. Previously only the property of monotonicity, not total monotonicity, had been used within these algorithms. We use the Θ(m) bound on finding the maxima of wide totally monotone matrices to speed up these algorithms by a factor of log n. © 1987 Springer-Verlag New York Inc.