Skip to main content
SpringerLink
Log in

The rectangle intersection problem revisited

  • Part I Computer Science
  • Published:
BIT Numerical Mathematics Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. H. S. Baird,Fast algorithms for LSI artwork analysis, Journal of Design Automation and Fault-Tolerant Computing 2, 2 (1978), 179–209.

    Google Scholar 

  2. J. L. Bentley,Algorithms for Klee's rectangle problems, Unpublished notes, Carnegie-Mellon University (1977).

  3. J. L. Bentley, D. Haken, and R. Hon,A fast program for reporting intersections among bounding boxes. In preparation (1979).

  4. J. L. Bentley and H. A. Maurer,Efficient worst-case data structures for range searching, Acta Informatica 13 (1980), 155–168.

    Google Scholar 

  5. J. L. Bentley and Th. Ottmann,Algorithms for reporting and counting geometric intersections, IEEE Transactions on Computers, C-28 (1979), 643–647.

    Google Scholar 

  6. 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.

    Google Scholar 

  7. H. Edelsbrunner,A new approach to rectangle intersections. Submitted for publication (1980).

  8. H. Edelsbrunner and H. A. Maurer,On region location in the plane, TU Graz, IIG Report No. 50 (1980).

  9. 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.

    Google Scholar 

  10. J. van Leeuwen and D. Wood,The measure problem for intersecting ranges in d-space, Journal of Algorithms (1980), to appear.

  11. M. I. Shamos and D. J. Hoey,Geometric intersection problems, Proc. 17th Annual IEEE FOCS (1976), 208–215.

  12. 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).

Download references

Author information

Authors and Affiliations

  1. Institut Für Angewandte Informatik Und Formale Beschreibungsverfahren, Universität Karlsruhe, D-7500, Karlsruhe, West Germany

    H. -W. Six & D. Wood

  2. Unit for Computer Science, McMaster University, L8S 4K1, Hamilton, Ontario, Canada

    H. -W. Six & D. Wood

Authors
  1. H. -W. Six
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. D. Wood
    View author publications

    You can also search for this author in PubMed Google Scholar

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

Reprints 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

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01933636

Keywords

Search

Navigation