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

Amitava Datta, R. Srikant, Kamala Krithivasan

Research output: Contribution to journalArticle

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)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.

Original languageEnglish (US)
Pages (from-to)49-61
Number of pages13
JournalInternational Journal of Computer Mathematics
Volume37
Issue number1-2
DOIs
StatePublished - Jan 1 1990
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Computer Science Applications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Fast sequential and parallel algorithms for finding the largest rectangle separating two sets'. Together they form a unique fingerprint.

  • Cite this