2
$\begingroup$

I have encountered the following challenging problem that I think to be a non straightforward generalization of the Knapsack problem.

Given an image with black background that contains blobs whose colors are taken from a set C (that does not contain black). Suppose that we have an infinite number of rectangular bounding boxes such that:

  • Each bounding box has a color taken from C.
  • Every bounding box of color c has width w_c and height h_c.

Question: How to place these bounding boxes on the image such that there is no overlap between any two boxes, and that n_good - n_bad is maximized, where n_good is the total number of pixels that are inside a box of the same color (as the pixel's color), and n_bad is the total number of pixels that are inside a box of a different color?

Any suggestions on how to solve this problem would be very much appreciated!

Thank you very much in advance for your help!

$\endgroup$
3
$\begingroup$

Just an extended note to show that the decision version of your problem ("Is there a placement of the bounding boxes such that $n_{good} - n_{bad} \geq k$?" ) is NP-complete even for two colors $C = \{c_1, c_2\}$ and two bounding boxes $B_1 \equiv \langle col=c_1, w=3, h=1 \rangle$, $B_2 \equiv \langle col=c_2, w=1, h=1 \rangle$.

The reduction is straightforward from: Danièle Beauquier, Maurice Nivat, Eric Rémila, Mike Robson: Tiling Figures of the Plane with Two Bars. Comput. Geom. 5: 1-25 (1995)

They prove that tiling a figure on the plane grid with two horizontal/vertical bars with length at least 3 is NP-complete.

The reduction to your problem is simple: just color the "pixels" of the figure with color $c_1$ and fill the remaining background pixels of the $N+1\times N+1$ square region around it with color $c_2$. You can place the bounding boxes $B_1, B_2$ with $n_{good} - n_{bad} = (N+1)^2$ if and only if the original figure is tileable with $3 \times 1$ horizontal/vertical bars.

$\endgroup$
  • $\begingroup$ Thank you very much for the reference! $\endgroup$ – Khue Jul 1 at 15:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.