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 language | English (US) |
---|---|
Pages (from-to) | 221-236 |
Number of pages | 16 |
Journal | Sadhana |
Volume | 17 |
Issue number | 1 |
DOIs | |
State | Published - Mar 1992 |
Externally published | Yes |
Keywords
- Efficient parallel algorithms
- maximum empty rectangle problem
- mesh-of-trees architecture
ASJC Scopus subject areas
- General