O(nlogn) divide-and-conquer algorithm computing union of rectangles

Question

I know there are lots of questions relevant to my question been asked and answered here, but I'm still confused. And I'm kind of new to computational geometry, any advice would be helpful.

Question:A set of n rectangles whose edges are parallel to x or y axis, and each with same length and height; coordinates of four corner points of each rectangles are known, design an O(nlogn)-time divide-and-conquer algorithm to compute the union of all the rectangles, union means the combined area covered by these rectangles.

These rectangles could be disjoint, touching or overlapping, and there are thousands of them. Output could be any shape(the result could be hollow inside, like an onion ring), with boundary defined by a set of point coordinates. I'm struggling on how to merge the two subparts when I split them by half and half. (I know how to compute the union area with sweep line/sweep plane method, but have no idea how to do it with DaC.)

Example:

A sweep line merge would be O(n) if each sub-output is sorted. — David Eisenstat
What is a union shape? Say, 1st rectangle is ( (0,0), (0,1), (1,0), (1,1) ), 2nd is ( (2,1), (2,2), (3,1), (3,2) ). If we take min x, min y, max x, max y, will it be desired union? ( (0,0), (0,2), (3,0), (3,2) ). Then just find min and max, it will be O(n). — Spock77
@DavidEisenstat I'm thinking of splitting all lowerleft points of rectangles half and half by drawing virtual vertical lines recursively, until there is only one rectangles at the left side of the vertical line, but haven't figured out how to merge left and right side area — OverCookedHam
@Alex union means all the areas covered by these rectangles, leaving out blanks, you can refer to the example picture — OverCookedHam

Spock77 Spock77 · Accepted Answer · 2014-03-10T22:55:27

Let's think like in well-known merge sort algorithm. Call our procedure UnionShape. Suppose we have vector< Shape > structures initially of size n (unsorted), so we can divide it by half and apply UnionShape recursively to it, giving lg n levels (let it be k). If we can elaborate Union procedure such that on each level we will have O(n) work, we'll get total of O (n lg (n)).

Idea is, that if corners of the shapes are sorted, we can elaborate Union procedure so that it take O(m) time, where m is the number of the corners of the united shapes. Initially (lowest k level - after k recursive calls) a total number of n/2^k, say 2, rectangles have corners already sorted. We have 2^k Union calls with n/2^k shape corners each, O(n) altogether. When uniting rectangles we are supporting the sort order of the corners of the resulting shape. On the next level we'll have 2^(k-1) calls with n/2^(k-1) shape corners (max) and so on - each level gives O(n) comparisons, and we have lg n levels, so we'll have O(n lgn) altogether.

That is the point for you and if you work out data structure and the Union procedure such way you'll be done.

O(nlogn) divide-and-conquer algorithm computing union of rectangles

1 Answers