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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.