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(log2 n) time using O(nlogn) processors. The perimeter version of this problem is solved in O(logn) time using O(nlog2 n) processors. On erew pram, we solve both the problems in O(logn) time using O(n2/logn) processors. We also present an O(logn) time algorithm on a mesh-of-trees architecture. © 1992 the Indian Academy of Sciences.

Kamala Krithivasan

Fulltext

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

Fast parallel algorithms for the Maximum Empty Rectangle problem

Sadhana

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. © 1990, Taylor & Francis Group, LLC

International Journal of Computer Mathematics

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

Information Sciences

An efficient algorithm for computing the maximum empty rectangle in three dimensions

In this paper, we present some efficient algorithms for the largest rectangle problem. The problems considered are the following. Problem P1: Given a bounding isothetic rectangle R and a point set S inside it, we have to find out the largest area (perimeter) isothetic rectangle inside R such that it does not contain any point from the set S. Problem P2: Given an isothetic polygon R, we have to find out the largest area (perimeter) rectangle completely contained in R. Problem P3: Same as problem P2, but isothetic holes are allowed inside the polygon R. We present algorithms that run in O(nlogn + K) time for all three problems. Where n is the cardinality of the set S in problem P1 and the number of sides of the polygon R and holes in problems P2 and P3. K is the number of candidate rectangles for a problem instance. The value of K is O(nlogn) on an average. So, our algorithms run in O(nlogn) time in the expected case. But the worst-case running time is O(n2). We also present optimal O(n) time systolic algorithms for all three problems. For problem P1, we present an efficient O(nlogn) time algorithm on a tree of processors. © 1992.

Journal	Data powered by TypesetSadhana
Publisher	Data powered by TypesetSpringer India
ISSN	02562499
Open Access	Yes