4

Assume that I have a set of rectangles (with different or same dimensions).

  1. The task is to find (and remove) the rectangle from the set that is larger or equal to a given rectangle.
  2. It should also be the smallest rectangle in the set than can encompass the given rectangle.

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?

eq_
  • 109
  • 6
  • You could easily reduce the search space by using the larger dimension (or the sum of both dimensions) of each rectangle as the key to build e.g. a tree or a sorted list. Of course, the worst case is still O(n). – Erich Kitzmueller May 26 '15 at 12:40
  • ammoQ: That was what I was trying to describe with "Another approach would be to use tree using one axis, and then test the other linearly." but instead of having a tree per width (for instance) it's sufficient to sort by width, then by height and go linearly from the smallest width that is greater or equal, and compare with height. – eq_ May 26 '15 at 12:46
  • Can your query rectangle be rotated 90 degrees or not? – j_random_hacker May 26 '15 at 12:47
  • No it can't (since I'm after speed here and the data that populates the rectangle comes from a third party black box module), but still out of interest, what optimizations did you have in mind? Exploiting the fact that you know that one dimension is always greater (or smaller) than the other? How? – eq_ May 26 '15 at 12:50
  • 2
    Try priority search tree (with priority=area and value=width). But it would be log(N) only if widths/heights of your rectangles are random enough. – Evgeny Kluev May 26 '15 at 12:53
  • Suppose your available rectangles were all rotated so that their width is <= their height, and sort them by width. Then rotate the query rectangle so that its width is >= its height. If you now binary search the array of available rectangles for the first rectangle i with width(i) >= width(query), this rectangle will definitely fit the query rectangle (possibly after rotating one of them) -- since height(i) >= width(i) >= width(query) >= height(query). However: It won't necessarily be a tight fit, and of course the binary search might not find a solution! – j_random_hacker May 26 '15 at 12:57
  • What's the formula that determines whether or not rectangle `a` contains rectangle `b`? It seems like if `h(a) >= h(b)` and `w(a) >= w(b)` then a contains b, (where h is the hypoteneuse), but I'm no mathematician. – Strawberry May 26 '15 at 14:31

1 Answers1

2

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 height

When 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.

Julian
  • 311
  • 2
  • 9
  • You won't get a tree but a graph this way – vib May 26 '15 at 14:59
  • Well a tree is a special form of a graph. The solution I suggested leads to a tree. There are plenty of examples of trees which can have more than two children for each non-leaf node; B-trees in databases for instance. – Julian May 27 '15 at 13:08
  • Sorry I had misunderstood your construction. – vib May 27 '15 at 13:39
  • Interesting idea, I need to think a bit more about this. – eq_ May 28 '15 at 08:00