DocumentCode :
1142501
Title :
An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles
Author :
Bentley, Jon Louis ; Wood, Derick
Author_Institution :
Departments of Computer Science and Mathematics, Carnegie-Mellon University
Issue :
7
fYear :
1980
fDate :
7/1/1980 12:00:00 AM
Firstpage :
571
Lastpage :
577
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 :
Computational geometry; VLSI design rule checking; geometric intersection problems; optimal algorithms; range searching; Algorithm design and analysis; Circuits; Computational complexity; Computational geometry; Computer aided software engineering; Computer science; Councils; Mathematics; Spatial databases; Very large scale integration; Computational geometry; VLSI design rule checking; geometric intersection problems; optimal algorithms; range searching;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/TC.1980.1675628
Filename :
1675628
Link To Document :
بازگشت