# Efficient queriable data structure to represent a screen with windows on it

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

Imagine a screen, with 3 windows on it: 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.

• 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? – Patrick87 Apr 14 '12 at 12:52
• @Patrick87: You're correct, and perhaps I'm approaching this in the wrong direction. I will edit the question. – daniel.jackson Apr 14 '12 at 13:00

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