color_me_red's blog

Finding if a square is contained in union of n other squares.
By color_me_red, history, 7 years ago, In English

If I have a square of some area a, and n other squares of the same area a, how can I check if the union of the n squares contains the initial square completely? I think I read that there is an solution for this, could someone help? Thanks!

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

You need to do a line sweep approach. Just google for it, you may find variations of it, but it isnt hard to change it a little bit. Interistingly the algorithm, as you mentioned, is needed for problem I from acm-icpc 2011 world finals.

There is material for this in wikipedia, cormen, geeksforgeeks (the last one is the main source from where I learnt)

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

    Could you explain a bit? I read on the line sweep algorithm but how would I adapt it for this purpose? (As we're dealing with planes and not lines here)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +15 Vote: I do not like it

      First of all, the squares should have sides parallel to xy axes. Then you consider squares as start and end segments, ordered by their x value. So you do the line sweep in the x direction keeping track of the active squares, the ones that appear in the current x. You keep the active squares in a bst (like c++ set) ordered by their y value, so you can add and remove squares in log(n) time. In this way you can calculate the area of the union of the n squares, something like as shown here.

      The key observation is that you keep track of the lenght of the union of the current active squares and, while you advance in the x coordinate, the area adds by d*l (where d is how much you advanced in x coordinate, and l the current total length). You keep updating the active set of squares and also the new total length by removing/adding squares to the active set and checking the neibours of the added/removed square (the neighbours in the bst (set) of active squares, ordered by y value). You check the neighbours to see if their length (y size) overlaps or doesn't (remembering that the set is ordered by y value, it is easy to see why you only check for neighbours to update the y current total length correctly). In this way you can update the current total lenght correctly in O(logn) per sqaure.

      To adapt for your problem you should consider the length only inside the square you are looking for (the one to check if it is overlaped by the union of all the others). If the area calculated by the line sweep inside the square is the same as the total area of the square, then, it overlaps completely.

      If you have any doubts, I would suggest to first think by yourself. If you are having troube perhaps you should practice on easier line sweep problems

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Rectangles union using sweep line is what you're looking for.

→ Reply