0
$\begingroup$

I'm trying to understand the algorithm that can be used to calculate the area of the union of a set of axis aligned rectangles.

The solution that I'm following is here : http://tryalgo.org/en/geometry/2016/06/25/union-of-rectangles/

The part I don't understand is :

The segment tree is the right choice for this data structure. It has complexity O(logn) for the update operations and O(1) for the query. We need to augment the segment tree with a score per node, with the following properties.

  • every node corresponds to a y-interval being the union of the elementary y-intervals over all the indices in the span of the node.
  • if the node value is zero, the score is the sum of the scores of the descendants (or 0 if the node is a leaf).
  • if the node value is positive, the score is the length of the y-interval corresponding to the node.

How do we achieve this in O(n log n) ?

My idea was to create a segment tree, and update each range's value as and when we encounter the range(y range as the height of the rectangle) while line sweeping. And then for for each interval(two consecutive elements in the sorted x array, multiple Δx by the total length of the y range active in this interval, by looking at the sum of all elements in the segment tree)

This would still leads us to having max(y) - min(y) elements in the segment tree's base.

Hence, I'm not sure how this is O(n log n) - where n is the number of rectangles.

Would greatly appreciate any help here.

I got an answer here : https://stackoverflow.com/questions/55702005/area-of-union-of-rectangles-using-segment-trees

But I'm not sure I understand @Photon's solution. What I don't understand is, what does each value inside each node of the segment tree mean ? And if we talk about the case where after meeting first rectangle on x=0, why does the segment tree get updated to the second figure ?

Per my understanding, the interval we're trying to update is [3, 6]. But that doesn't seem to be the case.

Thanks!

$\endgroup$
  • $\begingroup$ @D.W. I've added a comment to the original question. What I don't understand is, what exactly the value of each node in the segment tree in figure 1 specifies. Apologies for double posting. My intention was to just seek out help and improve visibility, since I thought it was a question that would be better suited to the Computer Science forum. $\endgroup$ – Anant Apr 17 at 1:32
  • $\begingroup$ @D.W. I've added a comment under their answer too. I've also edited this question to explain what I'm not understanding. Appreciate your help! $\endgroup$ – Anant Apr 17 at 1:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.