Fast parallel algorithms for the Maximum Empty Rectangle problem

Amitava Datta, R. Srikant, G. D.S. Ramkumar, Kamala Krithivasan

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)221-236
Number of pages16
JournalSadhana
Volume17
Issue number1
DOIs
StatePublished - Mar 1992
Externally publishedYes

Keywords

  • Efficient parallel algorithms
  • maximum empty rectangle problem
  • mesh-of-trees architecture

ASJC Scopus subject areas

  • General

Fingerprint

Dive into the research topics of 'Fast parallel algorithms for the Maximum Empty Rectangle problem'. Together they form a unique fingerprint.

Cite this