7
$\begingroup$

(this is related to my other question, see here)

Imagine a screen, with 3 windows on it:

enter image description here

I'd like to find an efficient data structure to represent this, while supporting these actions:

  • return a list of coordinates where a given window can be positioned without overlapping with others
    • for the above example, if we want to insert a window of size 2x2, possible positions will be (8, 6), (8, 7), ..
  • resizing a window on the screen without overlapping other windows while maintaining aspect ratio
  • insert window at position x, y (assuming it doesn't overlap)

Right now my naive approach is keeping an array of windows and going over all points on the screen, checking for each one if it's in any of the windows. This is $O(n\cdot m\cdot w)$ where $n, m$ are the width, height of the screen and $w$ is the number of windows in it. Note that in general $w$ will be small (say < 10) where each window is taking a lot of space.

$\endgroup$
  • $\begingroup$ Out of curiosity, why do you need the set of points? If it's to solve some other problem, there may be a fundamentally better approach. If there are no windows, won't it still be $O(nm)$ to construct the solution, that is, all points in the red rectangle? How do you want to represent the set of points? $\endgroup$ – Patrick87 Apr 14 '12 at 12:52
  • $\begingroup$ @Patrick87: You're correct, and perhaps I'm approaching this in the wrong direction. I will edit the question. $\endgroup$ – daniel.jackson Apr 14 '12 at 13:00
3
$\begingroup$

An easy optimization to the naive algorithm is to skip some points when you check one covered by a window. Say you scan left-to-right, top-to-bottom. If you encounter an $(x, y)$ in window $w = (l, r, w, h)$, you can jump from $x$ to $l + w + 1$ and continue. If windows are big and don't overlap, off the cuff, I'd wildly conjecture that would give you an $O(p)$ algorithm, where $p$ is the number of points in the set you return.

In fact, it could be beneficial to see whether the windows are generally wider or taller. For tall windows, it would be better to scan top-to-bottom, left-to-right; for wide windows, the method discussed above should win out. You might be able to take the idea and do scan/skip diagonally to get balanced performance across the board.

In fact, scanning left-to-right, top-to-bottom, you can remember for subsequent $h$ rows (values of $y$) that you will need to skip at the same $x$ value to the same $l + w + 1$ value, if you reach the $x$ (you might not if there's another window that overlaps). This would make top-to-bottom, left-to-right and diagonal scanning unnecessary to get equivalently good performance.

More generally, you now have two data structures: one with $O(1)$ preprocessing/construction overhead and $O(w)$ lookups, and one with $O(p)$ (possibly; maybe you can do better, or maybe my optimization doesn't really achieve this) preprocessing/construction and possibly $O(1)$ (hash/lookup table) or $O(\log p)$ (BST). So there are already two alternatives, both of which are pretty good, really...

$\endgroup$
  • $\begingroup$ How would you achieve what you described in the third paragraph? Right now I implemented your first suggestion by going over all windows and if there's an overlap, I do the skipping. This runs in a loop until the (x, y) coordinate of the current window I'm trying to fit doesn't change in a single iteration. $\endgroup$ – daniel.jackson Apr 14 '12 at 16:15
  • $\begingroup$ Maybe maintain a hash table of (y-counter, left, right) triples with the middle element determining the hash; add one and initialize to (y + h, x - 1, l + w + 1) when you hit a rectangle; check the table before scanning through rectangles; if y > y_max, ignore and remove; something like that, maybe. $\endgroup$ – Patrick87 Apr 14 '12 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.