Covering the unit square by smaller squares of variable sizes

Question

I'm trying to find whether a property $\mathcal{P}$ is true for all points of the unit square (in 2D). At each step I can query for a point of my choice. An oracle then answers me by either:

• telling me $\mathcal{P}$ doesn't hold for this point and thus the problem is solved: the property doesn't hold for all points in the unit square.
• tells me $\mathcal P$ holds for not only my query point but also for a small square containing my point. Thus I don't need to query for other points in this small square.

The problem is the small squares returned by the oracle are of variables sizes. What data structure and algorithm can I use to store the small squares returned? How can I track efficiently whether I have enough small squares to cover the unit square (and can thus stop the algorithm since I know the property holds for the whole unit square)? Or compute new points to query?

Edit: Okay, I realized my description of the problem is over-complicated. Basically this is the problem:

I have a certain number of squares of variable sizes and positions. How do I check whether they completely cover the unit square, or if not, how do I obtain the coordinates of a point of the unit square not covered ? PS: The problem is online.

Answer 1

I think a 2-dimensional (compressed) Quadtree can be useful here.

If you store a new rectangle in the tree, you can subdivide the space in the rectangle such that the boundary of the new rectangle does not lie in the interior of any subdivision, but lies only on the boundary of the subdivision. Checking whether there exists a 'non-covered' point can be done by storing the 'non-covered' as satellite data.

If you remove a rectangle from the tree, you need to check only for all 'quads' that the rectangle covered whether there exists (new) uncovered points.

Answer 2

I'd suggest a 2-dimensional k-d tree storing one point for each corner of each rectangle returned. A quadtree or 2-dimensional interval tree might also work. More generally, you might consider a 2-dimensional binary space partitioning tree, where you partition based on one of the edges of one of the squares returned (extended horizontally or vertically out to infinity in both directions).

How would you partition, in a binary space partitioning tree? Each square gives you two horizontal lines and two vertical lines (obtained by extending each edge of the square out to the full unit square). For instance, imagine sorting all of those vertical lines from left-to-right, and picking the median line, and using that to partition. Continue splitting recursively. This gives you a nested tree of regions. Then, associate each square with the lowest (deepest) node/region that fully contains it. When you are picking a split for a particular region of space, you use all of the lines that fall within that region (from all squares that have any overlap with that region).