## 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 language | English (US) |
---|---|

Pages (from-to) | 49-61 |

Number of pages | 13 |

Journal | International Journal of Computer Mathematics |

Volume | 37 |

Issue number | 1-2 |

DOIs | |

State | Published - Jan 1 1990 |

Externally published | Yes |

## 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