Find the rectangle with the smallest area that can hold another rectangle

4
votes

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?

1
algorithmsearchdata-structurescomputational-geometrybest-fit
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
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_
Can your query rectangle be rotated 90 degrees or not? – j_random_hacker
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_
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

1 Answers

2
votes

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.