Finding intersection of rectangles by range search

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.