Let $\mathcal X$ be a bounded subset of $R^n$ that is generated by a set of linear inequalities. For example, let ${\bf x} = (x_1, x_2, x_3, x_4, x_5)^\intercal \in \mathcal X$ iff \begin{align*} 0 &< x_1 < x_2 < x_4 < x_5 < 1 \\ 0 &< x_1 < x_3 < 1. \end{align*}
I want to find an algorithm that generates a set of $L$ disjoint hyperrectangles, denoted $R_1, \ldots R_L$ such that $$\mathcal X \approx \bigcup_{\ell=1}^L R_\ell.$$
The algorithm must have the properties:
- $\bigcup_{\ell=1}^L R_\ell$ is a strict subset of $\mathcal X$
- The approximation improves (under Lesbesgue measure $ \lambda$) as $L$ increases, $$\lim_{L\rightarrow\infty} \lambda\left(\left\{\mathcal X - \bigcup_{\ell=1}^L R_\ell\right\}\right) = 0$$
- The hyperrectangles must be disjoint and must be axis aligned.
The optimal solution for each $L$ would minimize the Lesbesgue measure of the set $\mathcal X -\bigcup_{\ell=1}^L R_\ell$. I can sense that an optimal solution for this problem, in general, is going to be very difficult to find. Rather, I am looking for a "reasonably good" (possibly greedy) solution which can be obtained fairly quickly.
Note: Although I would like to have some broad control over the number of rectangles in the approximation, the algorithm doesn't need to return exactly $L$ boxes.
My approach so far
My approach right now consists of
- Partitioning the unconstrained space into $L = M^n$ equidistant, same-size hyperrectangles (by partitioning each dimension into $M$ equally sized intervals).
- Checking to see if each vertex of each hyperrectangle is completely contained in $\mathcal X$.
This approach meets my minimum-criteria, but it is far from optimal, in the sense that the same approximation can be achieved with many fewer rectangles. I feel that the next step would be to try to combine the rectangles in some way, but I just don't have good enough intuition in high-dimensions to figure out a good way of doing this.