Fast parallel algorithms for the Maximum Empty Rectangle problem

We present efficient parallel algorithms for the maximum empty rectangle problem in this paper. On crew pram, we solve the area version of this problem in O(log 2 n) time using O(nlogn) processors. The perimeter version of this problem is solved in O(logn) time using O(nlog 2 n) processors. On erew pram, we solve both the problems in O(logn) time using O(n 2/logn) processors. We also present an O(logn) time algorithm on a mesh-of-trees architecture. © 1992 the Indian Academy of Sciences.