Assume that I have a set of rectangles (with different or same dimensions).
This is easily solved in O(n) time by doing a linear search / update, but is it possible to achieve better results? O(log n) would be optimal I'd assume. Insert and removal must also be faster than O(n) for this to be of any use in my case.
Can any shortcuts be made by not finding the optimal rectangle, but rather relax the 2nd restriction to: "It should also be one of the smallest rectangles that can encompass the given rectangle"-
I was thinking along the lines of using a Z-order curve (of the width/height) and use as a one dimensional index and combine that with a tree. Would that work? Or would there be too much waste?
Another approach would be to use tree using one axis, and then test the other linearly.
Anyone done something similar and can share their experience?
Here's an idea which is not fully elaborated yet:
Maybe you could use a fourfold-branched tree with 2-tuple values (height and width) each representing one rectangle.
One node (w, h) has 4 child-nodes:
(<w, <h) - contains rects which have smaller width and smaller height(>=w, <h) - contains rects which have greater width and smaller height(<w, >=h) - contains rects which have smaller width and greater height(>=w, >=h) - contains rects which have greater width and greater heightWhen you descend at a (w, h) rect node to look for a container for your (w2, h2) rect there are 4 different cases now:
w2<w and h2<h - three options: (>=w, <h), (<w, >=h), (>=w, >=h)w2>=w and h2<h - two options: (>=w, <h), (>=w, >=h)w2<w and h2>=h - two options: (<w, >=h), (>=w, >=h)w2>=w and h2>=h - one option: (>=w, >=h)You would have to descend to all possible branches, which is still better than O(n).
Inserting is O(log n). Not sure about deleting and balancing yet. But I am almost certain there is a solution for that as well.