1
$\begingroup$

I have the following problem:

In the space $E=\{1, 2, \dots, N_x\} \times \{1, 2, \dots, N_y\}$, I want to define $N_R$ rectangles $R_k=\{x_k^0, \dots, x_k^1\}\times\{y_k^0, \dots, y_k^1\}$ which cover part of my space $E$.

The total size of the union of all rectangles has a upper bound $C$ (constraint i). And the rectangle size is of course lower-bounded to $s_x$ on the 1st dimension (constraint ii) and $s_y$ on the 2nd one (constraint iii).

Each point of the space $E$ is associated with a score value by the function $f: E \rightarrow \mathbb R_+$.

I want to maximize this objective function:

$$\max_{N_R}\max_{R_1, \dots, R_{N_R}\\ s.t. |\bigcup_{k=1}^N R_k|\le C \> (i) \\ |x_k^1 - x_k^0| \ge s_x \quad (ii) \\ |y_k^1 - y_k^0| \ge s_y \quad (iii)} \sum_{z\in E}\sum_{k=1}^{N_R}1_{z\in R_k}f(z)$$

To express it in a non-mathematical way, I want to find a set of rectangles such that the sum of the scores of the points they contain is maximal.

In my case, $E$ is quite big and I must do that for several different score functions f, so that it is impossible to brute-force all possibilities.

I do not know how to wisely optimize this function. Do you have some pieces of advice? Or could you lead me to existent algorithms to do that?

I have thought of (and implemented) suboptimal processes such that fixing a rectangle size (10 x 10 for instance) and solving the problem in this simpler setting.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.