Fast sequential and parallel algorithms for finding the largest rectangle separating two sets

Given a bounding isothetic rectangle BR and two sets of points A and B with cardinalities n and m inside it, we have to find an isothetic rectangle containing maximum number of points from set A and no point from set B. We consider two limiting cases of this problem when the cardinalities of set A (resp. set B) is much greater than that of set B (resp. set A). We present efficient sequential and parallel algorithms for these two problems. Our sequential algorithms run in O((n + m)logm + m2) and O((m + n)logn + n2) time respectively. The parallel algorithms in CREW PRAM run in O(Iogn) and O(logm) time using O(max(n, m2/logm)) and O(max(m, n2/logn)) processors respectively. Our sequential algorithms are faster than a previous algorithm under these constraints on cardinality. No previous parallel algorithm was known for this problem. We also present an optimal systolic algorithm for the original problem. © 1990, Taylor & Francis Group, LLC