Fast parallel algorithms for the Maximum Empty Rectangle problem

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

doi:10.1007/BF02811344

Fast parallel algorithms for the Maximum Empty Rectangle problem

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

Research output: Contribution to journal › Article › peer-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² n) time using O(nlogn) processors. The perimeter version of this problem is solved in O(logn) time using O(nlog² n) processors. On erew pram, we solve both the problems in O(logn) time using O(n²/logn) processors. We also present an O(logn) time algorithm on a mesh-of-trees architecture.

Original language	English (US)
Pages (from-to)	221-236
Number of pages	16
Journal	Sadhana
Volume	17
Issue number	1
DOIs	https://doi.org/10.1007/BF02811344
State	Published - Mar 1992
Externally published	Yes

Keywords

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

ASJC Scopus subject areas

General

Online availability

10.1007/BF02811344

Library availability

Discover UIUC Full Text

Cite this

@article{ed607cd2dd284eabb9c4151b23d70d6d,

title = "Fast parallel algorithms for the Maximum Empty Rectangle problem",

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.",

keywords = "Efficient parallel algorithms, maximum empty rectangle problem, mesh-of-trees architecture",

author = "Amitava Datta and R. Srikant and Ramkumar, {G. D.S.} and Kamala Krithivasan",

year = "1992",

month = mar,

doi = "10.1007/BF02811344",

language = "English (US)",

volume = "17",

pages = "221--236",

journal = "Sadhana",

issn = "0256-2499",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - Fast parallel algorithms for the Maximum Empty Rectangle problem

AU - Datta, Amitava

AU - Srikant, R.

AU - Ramkumar, G. D.S.

AU - Krithivasan, Kamala

PY - 1992/3

Y1 - 1992/3

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

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

KW - Efficient parallel algorithms

KW - maximum empty rectangle problem

KW - mesh-of-trees architecture

UR - http://www.scopus.com/inward/record.url?scp=51649154235&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51649154235&partnerID=8YFLogxK

U2 - 10.1007/BF02811344

DO - 10.1007/BF02811344

M3 - Article

AN - SCOPUS:51649154235

SN - 0256-2499

VL - 17

SP - 221

EP - 236

JO - Sadhana

JF - Sadhana

IS - 1

ER -

Fast parallel algorithms for the Maximum Empty Rectangle problem

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this