proveus's blog

Mathemetics
By proveus, history, 10 months ago, In English

Hello everyone. Today i meet a problem like find the intersection areas of n rectangles. i use IT tree but i can't not solve with case have a area that more than 3 rectangles intersection. Very thanks you help me to solve this proplem.

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Intersection of two rectangles is a rectangle. I don't think any further explanation is really necessary. A bit of casework and the problem is done.

Good luck!

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hmm sorry when my question is not clear. It mean you have n rectangles, you find the intersection areas of n rectangles.

    → Reply
»
10 months ago, # |
  Vote: I like it +5 Vote: I do not like it

By mentioning IT tree, which I suppose is segment tree, I think you realized this problem can be solved with sweep line and range queries. A classic problem would be to find union of $$$n$$$ rectangles instead of intersection. If you know how to solve for union, I think you can also solve for intersection.

→ Reply