Finding Rectangle Intersections by Divide-and-Conquer

Publisher Website
Google Scholar
Abstract
In this correspondence we reconsider three geometrical problems for which we develop divide-and-conquer algorithms. The first problem is to find all pairwise intersections among a set of horizontal and vertical line segments. The second is to report all points enclosures occurring in a mixed set of points and rectangles, and the third is to find all pairwise intersections in a set of isooriented rectangles. We derive divide-and-conquer algorithms for the first two problems which are then combined to solve the third. In each case a space-and time-optimal algorithm is obtained, that is O(n) space and O(n log n + k) time, where n is the number of given objects and k is the number of reported pairs. These results show that divide-and-conquer can be used in place of line sweep, without additional asymptotic cost, for some geometrical problems. This raises the natural question: For which class of problems are the line sweep and divide-and-conquer paradigms interchangeable?

This publication has 5 references indexed in Scilit: