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

i know there lots of questions relevant question been asked , answered here, i'm still confused. , i'm kind of new computational geometry, advice helpful.

question:a set of n rectangles edges parallel x or y axis, , each same length , height; coordinates of 4 corner points of each rectangles known, design o(nlogn)-time divide-and-conquer algorithm compute union of rectangles, union means combined area covered these rectangles.

these rectangles disjoint, touching or overlapping, , there thousands of them. output shape(the result hollow inside, onion ring), boundary defined set of point coordinates. i'm struggling on how merge 2 subparts when split them half , half. (i know how compute union area sweep line/sweep plane method, have no idea how dac.)

example:

let's think in well-known merge sort algorithm. call our procedure unionshape. suppose have vector< shape > structures of size n (unsorted), can divide half , apply unionshape recursively it, giving lg n levels (let k). if can elaborate union procedure such on each level have o(n) work, we'll total of o (n lg (n)).

idea is, if corners of shapes sorted, can elaborate union procedure take o(m) time, m number of corners of united shapes. (lowest k level - after k recursive calls) total number of n/2^k, 2, rectangles have corners sorted. have 2^k union calls n/2^k shape corners each, o(n) altogether. when uniting rectangles supporting sort order of corners of resulting shape. on next level we'll have 2^(k-1) calls n/2^(k-1) shape corners (max) , on - each level gives o(n) comparisons, , have lg n levels, we'll have o(n lgn) altogether.

that point , if work out data structure , union procedure such way you'll done.