# Find the key points of the outer layer of n overlapping rectangles – Divide and Conquer Given a set of $$n$$ rectangles depicted as: $$[Li, Ri, Hi]$$ whereby the corners of the $$i-th$$ rectangle are – $$(Li, 0), (Ri,0), (Li, Hi)$$ and $$(Ri, Hi)$$.

The goal is to print all of the key points of the outer layer of the $$n$$ overlapping rectangles (given in a list).

Key points $$(Xj, Yj)$$ are the points that collectively portray the outer layer of the rectangles – look at the example below:

Given the two blocks [4, 13, 4] and [2, 7, 10] the output should be: [2,0], [2,10], [7,10], [7,4], [13,4] and [13,0] (The points that are marked red).

This should be done in $$O(nlogn)$$ time where $$n$$ is the number of buildings (rectangles). I have tried to solve this problem by –

(1) Sorting the blocks by priority: $$Li$$ then $$Ri$$ then $$Hi$$.

(2) Compare any two blocks: $$[Li, Ri, Hi]$$ and $$[Li+1, Ri+1, Hi+1]$$ (15 different cases like Li==Li+1 and Hi< Hi+1 and stuff like this).

(3) Remove/add points according to condition (using AVL)

This works in some cases, but in others it fails miserably. I think this can be solved by Convex Hull algorithms, we have only learned the divide and conquer method so far – but I cannot link between this question and this method. I hope you can help me with this one!

Thank you Posted on Categories proxies