# Covering the unit square by smaller squares of variable sizes

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.

• I'm looking into this. Maybe I can solve my problem with Voronoi diagrams where each point defines its own metric. – Adrien Feb 24 '17 at 9:44