Abstract
We take another look at the problem of intersecting rectangles with parallel sides. For this we derive a one-pass, time optimal algorithm which is easy to program, generalizes tod dimensions well, and illustrates a basic duality in its data structures and approach.
Similar content being viewed by others
References
H. S. Baird,Fast algorithms for LSI artwork analysis, Journal of Design Automation and Fault-Tolerant Computing 2, 2 (1978), 179–209.
J. L. Bentley,Algorithms for Klee's rectangle problems, Unpublished notes, Carnegie-Mellon University (1977).
J. L. Bentley, D. Haken, and R. Hon,A fast program for reporting intersections among bounding boxes. In preparation (1979).
J. L. Bentley and H. A. Maurer,Efficient worst-case data structures for range searching, Acta Informatica 13 (1980), 155–168.
J. L. Bentley and Th. Ottmann,Algorithms for reporting and counting geometric intersections, IEEE Transactions on Computers, C-28 (1979), 643–647.
J. L. Bentley and D. Wood,An optimal worst-case algorithm for reporting intersections of rectangles, IEEE Transactions on Computers, C-29 (1980), 571–577.
H. Edelsbrunner,A new approach to rectangle intersections. Submitted for publication (1980).
H. Edelsbrunner and H. A. Maurer,On region location in the plane, TU Graz, IIG Report No. 50 (1980).
U. Lauther, 4-dimensional binary search trees as a means to speed up associative searchs in design rule verification of integrated circuits, Journal of Design Automation and Fault-Tolerant Computing 2, 3 (1978), 241–247.
J. van Leeuwen and D. Wood,The measure problem for intersecting ranges in d-space, Journal of Algorithms (1980), to appear.
M. I. Shamos and D. J. Hoey,Geometric intersection problems, Proc. 17th Annual IEEE FOCS (1976), 208–215.
V. K. Vaishnavi and D. Wood,Rectilinear line segment intersection, layered segment trees and dynamization, McMaster University Computer Science Technical Report No. 80-CS-8, (1980).
Author information
Authors and Affiliations
Additional information
The work of the first author was supported by the DAAD (Deutscher Akademischer Austauschdienst) and carried out while visiting McMaster University as a postdoctoral fellow. The work of the second author was supported by a Natural Sciences and Engineering Research Council of Canada Grant No. A-7700.
Rights and permissions
About this article
Cite this article
Six, H.W., Wood, D. The rectangle intersection problem revisited. BIT 20, 426–433 (1980). https://doi.org/10.1007/BF01933636
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01933636