sanya_marmeladov's blog

By sanya_marmeladov, history, 7 weeks ago, In English

Hello everyone, I recently faced the problem of finding the area covered by several rectangles. Here is an example text: there is a canvas, rectangles are drawn on it (intersections are possible) and you need to find a shaded area. For example, if one rectangle is drawn on top of another, then the coverage area is equal to the area of one of the rectangles. Is there a universal way to solve for N rectangles?

Problem: The Beitsburg Art Museum hosts an exhibition of works by postmodern artists. The suprematist Baitevich makes a new canvas "Rectangles" especially for the exhibition. During the first day of work, Baitievich painted over one rectangle in gray. During the second day of work, Baytovich painted over another rectangle with a brown color. During the third day of work, Baytievich painted over the third rectangle in crimson, after which he announced that the masterpiece was completed. The organizers of the exhibition agreed to pay Baitevich an amount proportional to the area of the area painted over on the canvas. Since rectangles can intersect, the task turned out to be not so simple, so you are assigned to calculate the corresponding area.

 
 
 
 
  • Vote: I like it
  • -25
  • Vote: I do not like it

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I don't really understand what the task is. "then the coverage area is equal to the area of one of the rectangles" — which one? And how does this relate to the shaded area? Best you post the problem link.

If you mean to find the intersection of all rectangles, then you can notice, that the intersection of two rectangles is always a rectangle.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is an explanation of the problem. The problem itself was described earlier: the coverage area of several (more than 2) rectangles

»
7 weeks ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

I'm not sure about the problem. But I think if you visualize the about the 2 directions (x and y directions) independently. Imagine n rectangles as intervals , one in x (horizontal) direction covering some range [a,b] and one in y direction covering some range [c,d].

Also every vertical interval is mapped with a pair of x coordinates (call it l,r) (i.e it's left and right x coordinate of the rectangle of which the interval is a part).

Then the problem reduces to finding a segment (call it [p,q] in horizontal direction which intersects with n-1 horizontal intervals (n are total no of rectangles) and the corresponding vertical segment.

That vertical segment must intersect n-1 vertical intervals and its l,r value must satisfy l<=p AND r>=q. If such segments do not exist then no region overlaps all the rectangles.

The area of intersection of all rectangles simply equals product of the lengths of both the segments.

To do all this stuff, sort the starting and endings of every interval and iterate over them and keep track of "overlap" variable, everytime you encounter a starting point, overlap++, and if you get ending point then overlap--.

I guess it can be done simply in O(NlogN).

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You misunderstood the problem. I have completed added the problem to the post

»
7 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

I am guessing that it will be the problem of finding the area of the union of n rectangles, You can solve this in O(N*logN) using a lazy propagation segment tree and sweep line

The idea is to treat each vertical column separately. You can store all beginnings and endings of the rectangles in a sorted order, then start looking from left to right, when a rectangle starts you update the segment tree with its range (add 1 to all indexes [l,r]), when a rectangle ends, you remove the update (add -1 to all indexes [l,r]), then query the area of the vertical column (maxn)x1, this area is the number of indexes different of 0 in the segment tree ,it is easier to query how many zeroes and then remove from how many indexes you have, you can do this operation by storing in the node the minimum and how many times it appears, then querying [0,maxn].

The way i explained depends on the value of maxn, but there is a way to do it in actual polynomial time by compressing the coordinates.

Here is a link for a more complete explanation: https://tryalgo.org/en/geometry/2016/06/25/union-of-rectangles/

There is also this problem is CSES in case you want to try to implement: https://cses.fi/problemset/task/1741

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can skip the segement tree if all you need to update is {l, r} since you can just make an a "currentSum" array and add 1 to array[l] and subtract 1 from array[r + 1]. Then you just traverse each column.

    This is also an USACO problem, just worded a little differently. I forgot what year, but I think it was a silver.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You misunderstood the problem. I have completed added the problem to the post

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sanya_marmeladov (previous revision, new revision, compare).