sarnath@sybil.cs.buffalo.edu (Ramnath Sarnath) (06/28/90)
Consider the following problem: Given a matrix in which all the rows are in non-decreasing order, left to right, and all columns are non-decreasing top to bottom. We wish to 1. Search for some element "x" in the matrix. 2. Select the k-th largest element in the matrix. I would like to know if any of you have seen such structures arising naturally in any problem, or seen parallel algorithms for these problems. If so, what are the time and processor bounds acheived (assuming an nxn matrix) ? thanx, sarnath