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

Abstract

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)log m + m ²) and O((m+ n) log n + n ²) time respectively. The parallel algorithms in CREW PRAM run in o(log n) ando(log m ²) time using O(max(n,m ²/logm)) and O(max(m,n ²/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.

Keywords:

• Computational geometry
• isothetic rectangles
• line sweep paradigm
• CREW PRAM
• systolic array

C.R. Categories:

• B.7.1 [Very Large Scale Integration]
• C.1.1 [Single Data Stream Architcctures]
• F.2.2 [Analysis of Algorithms and Problem Complexity]
• 1.3.5 [Computational Geometry and Object Modelling]