An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles
- 1 July 1980
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-29 (7) , 571-577
- https://doi.org/10.1109/tc.1980.1675628
Abstract
In this paper we investigate the problem of reporting all intersecting pairs in a set of n rectilinearly oriented rectangles in the plane. This problem arises in applications such as design rule checking of very large-scale integrated (VLSI) circuits and architectural databases. We describe an algorithm that solves this problem in worst case time proportional to n lg n + k, where k is the number of interesecting pairs found. This algorithm is optimal to within a constant factor. As an intermediate step of this algorithm, we solve a problem related to the range searching problem that arises in database applications. Although the algorithms that we describe are primarily theoretical devices (being very difficult to code), they suggest other algorithms that are quite practical.Keywords
This publication has 4 references indexed in Scilit:
- Efficient worst-case data structures for range searchingActa Informatica, 1980
- Algorithms for Reporting and Counting Geometric IntersectionsIEEE Transactions on Computers, 1979
- On the complexity of computing the measure of ∪[a i ,b i ]Communications of the ACM, 1978
- Geometric intersection problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976