Publication
Journal of Algorithms
Paper

Finding intersection of rectangles by range search

View publication

Abstract

Three related rectangle intersection problems in k-dimensional space are considered: (1) find the intersections of a rectangle with a given set of rectangles, (2) find the intersecting pairs of rectangles as they are inserted into or deleted from an existing set of rectangles, and (3) find the intersecting pairs of a given set of rectangles. By transforming these problems into range search problems, one need not divide the intersection problem into two subproblems, namely, the edge-intersecting problem and the containment problem, as done by many previous studies. Furthermore, this approach can also solve these subproblems separately, if required. For the first problem the running time is O((log n)2k-1 + s), where s is the number of intersecting pairs of rectangles. For the second problem the time needed to generate and maintain n rectangles is O(n(log n)2k) and the time for each query is O((log n)2k-1 + s). For the third problem the total time is O(n log n + n(log n)2(k-1) + s) for k ≥ 1. © 1981.

Date

01 Jan 1981

Publication

Journal of Algorithms

Authors

Share