An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles
Jon Louis Bentley, Wood · IEEE Transactions on Computers · 1980
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.
Cited by 244 works. doi:10.1109/tc.1980.1675628
Authors
References
- Introduction to V.L.S.I. Systems
- The Art of Computer Programming: Volume 3: Sorting and Searching
- Geometric intersection problems
- Algorithms for Reporting and Counting Geometric Intersections
- The Art of Computer Programming, Volume 3, Sorting and Searching
- Efficient worst-case data structures for range searching
- Fast algorithms for LSI artwork analysis
- A New Approach to Planar Point Location
- On the complexity of computing the measure of ∪[a i ,b i ]
- The measure problem for rectangular ranges in d-space