Parallel Algorithms for Searching Monotone Matrices on Coarse Grained Multicomputers

We present parallel algorithms for geometric problems on coarse grained multicomputers. More specifically, for a square mesh-connected p-processor computer, we show that:The implicit row maxima problem on a totally monotone n × n matrix can be solved in O((n/p) log p) time, if n > p2 .The all-farthest-neighbors problem for a convex n -gon can be solved in O(n/sqrt(p)) time, if n > p2/4 .The maximum-perimeter triangle inscribed in a convex n -gon can be found in O(n/sqrt(p)) time, if n > p2 .The solutions to the two latter problems are based on the reduction of these problems to searching problems in totally monotone matrice