empaktus's blog

Question about rectangle containment problem.
By empaktus, history, 15 months ago, In English

I was trying to solve 2024 Argentinian Programming Tournament (TAP) problem H (https://codeforces.me/gym/105321) and got stuck on a subproblem, but the contest doesn't have an editorial.

I have N axis-aligned rectangles that don't intersect each other (not even at corners), but some can be nested inside others. I need to efficiently find the "parent" of each rectangle, meaning the smallest rectangle that completely contains it. The trivial approach would be O(N^2): for each rectangle, check all others to see which contain it, but this would be too slow. I was thinking about sweep line algorithms but I can't figure it out.

Is there a standard algorithm for this problem?

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

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

Someone posted a similar problem a few weeks ago. That is for convex polygons, but will give you some ideas. Although, I think it's way simpler for axis-aligned rectangles.

https://codeforces.me/blog/entry/144863

→ Reply
»
15 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Something like this might work. I do not have time to put much thinking rn.

For each rectangle, mark the left side with red (R) and the right side with blue (B). Loop through the rectangles from right to left (sorted by right side). When processing a rectangle, check the first line to its right from any point on its B side.

  1. If it can't find a line, this rectangle is a root.
  2. If it hits a line (let's say it hit rectangle Z):
    • If it hits an R line, the parent is Z's parent.
    • If it hits a B line, the parent is Z.

The sweep can be maintained using a segment tree.

→ Reply