title: O(nlogn) divide-and-conquer algorithm computing union of rectangles
body: <p>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.</p>
  
  <p>Question:A set of <code>n</code> 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.</p>
  
  <p>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.)</p>
  
  <p>Example:</p>
  
  <p><img src="https://i.stack.imgur.com/cIRjG.png" alt=""></p>