cvosh's blog

Real life problem. Is there algorithm for it?
By cvosh, history, 3 years ago, In English

Hi There.

I am a software developer and now working on some project related to documents generation and viewing. There at some point I have a function that needs to find rectangles that do not contains some other rectangles. We implemented it in O(n^2), but I feel it is possible to do much faster. Here is the problem:

I have an array of rectangles. These rectangles can intersect and overlap. Some are inside each other. Need to write an function, that will return an array of rectangles, that do not contain other rectangles (partial intersect do not count). Exactly same rectangles also count.

I am not sure is it possible to do faster, or is there any algorithm for it. Maybe some kind of sweepline or convex hull, but that's just a guess. That's why t decided to ask the Codeforces community. Looking forward to your ideas. I hope it is a right place for such things.

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

Comments Comments (7)
| Write comment?
»
3 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

Here is my n*log(n)^2 solution:

Imagine a 2d data structure that can answer following queries:

  1. add point with coordinates (X, Y) and value A
  2. find the greatest value among points inside some rectangle

This can be implemented with 2d implicit segment tree or some other structures.

Now sort all rectangles from input by right side coordinate. Let coordinates of current rectangle will be (X1, Y1) for bottom-left point and (X2, Y2) for top right point (rectangles are sorted so that X2 increases). In order from left to right do following:

  1. Ask our DS minimum value of point inside current rectangle. Then current rectangle contains other rectangle if and only if this value is less (or less or equal, depending on containment definition) than Y2.
  2. Add to our DS point with coordinates (X1, Y1) and value Y2

Might be hard to implement, but it should work

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

    Thanks for idea. Are you sure about the complexity of n*log(n)^2. I mean that log(n)^2

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

      Query (of any type) to 2d implicit segment tree takes $$$O(log^2X)$$$, where $$$X$$$ is the maximum coordinate, but if you compress coordinates you will get $$$O(log^2n))$$$. We will make $$$n$$$ queries in total. So overall complexity is $$$O(n\cdot log^2n)$$$

      → Reply
»
3 years ago, # |
  Vote: I like it +49 Vote: I do not like it

Just put it on a GPU and it will be probably faster than any $$$\log^2(n)$$$ data structure

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

    unfortunately, it will be running inside browser. with javascript

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +27 Vote: I do not like it

      Also keep in mind that brute force will probably be faster than any complex algorithm for small $$$n$$$, possibly up to a few thousand. If you want to squeeze out more performance, consider using WebAssembly. This will give you a huge boost (probably 10x or more) over normal JS.

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

I wish this was a problem in some Div1 and I could check how the top guys solve it. :)

→ Reply