How to enumerate disjoint sets which cover a vector space in $\mathbb{R}^n$?

Question

My experience with OR is pretty limited, so I apologize if I'm using any sort of bespoke terminology.

I have a set of subsets ${ \{ S_1,\cdots,S_m\}}$ of $\mathbb{R}^n$, and corresponding functions $\{f_1,\cdots,f_m\}$, where the domain of $f_i$ is $S_i$.

Every set $S_i$ can be understood as a hypercube in $\mathbb{R}^n$; no discontinuities or funkiness happening there.

Assume that for every set $S_i$, across every dimension of the vector space, your index variable $x_h$ has some concrete constraints

$$a_{x_h} \leq x_h \lt b_{x_h} \forall h \in\{1,\cdots,n\}$$

Additionally, all of these sets are disjoint, eg $$S_i \cap S_j = \emptyset, i \neq j$$

The problem is that these sets don't necessarily cover $\mathbb{R}^n$, eg it's possible that

$$\bigcup_{i=1}^m S_i \neq\mathbb{R}^n$$

What I want is to enumerate the minimum number of disjoint subsets $\{S_{m+1}..S_{m+k}\}$ required to "cover" $\mathbb{R}^n$, eg

$$\bigcup_{i=1}^{m+k} S_i = \mathbb{R}^n$$

As an example, let's take $\mathbb{R}^2$ as the space we want to cover.

Our set of functions $f_i$ might have the following domains:

D1 : { (x, y) : x >= 2, y < -4 }

D2 : { (x, y) : x < -1, y > 5 }

D3 : { (x, y) : -1 <= x < 2 }

From inspection, it's clear that there's at least 2 disjoint subsets of $\mathbb{R}^2$ that are not covered by these domains.

They're depicted by the purple question marks in this image:

What I want to know is, is there an algorithm which can take these domains as input, and output all existing disjoint, uncovered domains in the larger space?

Answer 1

This can be solved with an integer linear program (although I'm not sure that's the best approach). We first create a grid by running horizontal and vertical lines through all corners of your various domains. We don't need the grid to be evenly spaced. We also need to enclose the overall region in a box (hyperrectangle) big enough that all the vertices of the function domains are in the interior of the box. (We will relax the box later.) We need grid lines along the edges of the box.

I'll refer to any hyperrectangle bounded by consecutive grid lines in all directions as a "cell". We record the center points of each cell for future use, discarding any that are inside function domains.

Next, we form all possible hyperrectangles whose vertices are grid points. Discard any hyperrectangle that overlaps one of the function domains. This is easy to determine. If, in any dimension, both limits of the hyperrectangle are on the same side of the domain (both less than or equal to the lower range limit for that variable, or both greater than or equal to the upper range limit), the domain and the hyperrectangle do not overlap. Otherwise, they do.

Enumerate the surviving hyperrectangles as $R_1,\dots,R_N.$ Compute the set $S$ of pairs $(i,j),\, i<j$ for which $R_i$ and $R_j$ overlap (using the same logic by which we decided if hyperrectangles and domains overlapped).

Finally, for each center point $c_i,$ compute the set $C_i = \lbrace j\in 1,\dots,N : c_i\in R_j\rbrace$ of hyperrectangles containing that point.

Now define binary variables $x_i,\,i=1,\dots,N$ which will indicate whether or not hyperrectangle $R_i$ is part of our cover. The objective is to minimize $\sum_i x_i,$ the number of rectangles used. To avoid hyperrectangles intersecting, for each $(i,j)\in S$ we add the constraint $x_i + x_j \le 1,$ preventing us from using both. Finally, to ensure that everything outside the function domains is covered, for each center point $c_i$ we add the constraint $\sum_{j\in C_i} x_j = 1,$ requiring that the center point belong to exactly one selected hyperrectangle. Since the hyperrectangle boundaries are grid lines, if the center point of a cell is in a hyperrectangle, the entire cell is in the hyperrectangle.

Once we have a solution, we replace the lower (upper) limit of any variable in any selected hyperrectangle with $-\infty$ ($+\infty$) if the edge of the hyperrectangle is on one of the boundaries of the box we imposed at the start.