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.
Here is my n*log(n)^2 solution:
Imagine a 2d data structure that can answer following queries:
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:
Might be hard to implement, but it should work
Thanks for idea. Are you sure about the complexity of n*log(n)^2. I mean that log(n)^2
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)$$$
Just put it on a GPU and it will be probably faster than any $$$\log^2(n)$$$ data structure
unfortunately, it will be running inside browser. with javascript
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.
I wish this was a problem in some Div1 and I could check how the top guys solve it. :)