Minimum number of rectangles in a polygon

Question

Given a polygon and dimension $d$, find a minimum partition of rectangles that has either of its dimensions equal to $d$.

Example: Consider the following diagram:

I want to cover maximum shaded region using minimum number of rectangles of fixed one dimension (width or height). In other words, one dimension of all the rectangles should be the same. Rotated rectangles are not allowed. We can leave empty space if required near the inclined edge. No overlapping is allowed.

My attempt was to use a linear program to solve this problem. However, I'm stuck at the very beginning to put a restriction on the number of rectangles. I thought of declaring a binary variable $m_i, i \in \{1, 2, ..., N \}$, where $m_i=1$ shows that $i$th rectangle is present out of $N$ available rectangles. The solution breaks down if my solution requires more number of rectangles than $N$. My questions are as follows:

1. Is linear programming the only way to solve this problem? Can I use some other algorithm to solve it?
2. If linear programming is the only way, how should I handle the varying number of rectangles in the linear program?

Answer 1

Since many readers of this forum use dimension to mean many things, instead of dimension I would say rectangles of size $n_ i$ by $d$, where $d$ is given, and where you clearly specify the objective, which appears to me to be something like maximum over allowed coverings of (total area covered by the over of k non overlapping rectangles with sides parallel to a given set of coordinate axes)/k. If you just want to minimize number of rectangles, place 0 or 1 d by epsilon rectangles wherever they fit.

I do not know how to formulate a linear program to achieve your objective, but I know how I would start. First I would try two striping solutions, one where the edges of the rectangles have the d edge all horizontal and one all vertical. This has the benefit that you get some achievable solutions readily and can establish a benchmark for an optimal covering to surpass. You may find more than one cover to use even if all the d edges are e.g. horizontal , so finding a good striping takes some work.

Now you can attempt a greedy refinement by picking a large rectangle from the striped covering and then consider the sub problem on the complement. While this is potentially combinatorially explosive, you might achieve success when one or more connected components are small.

Gerhard "Sounds Like A Paintbrush Problem" Paseman, 2016.10.07.

Answer 2

Presumably you want an exact cover, i.e., no rectangles in the cover fall outside the shaded region. (Otherwise one rectangle covering the bounding box suffices.)

I don't think your precise problem has been considered in the literature (I was just working on a survey, so I was scanning the literature). However, almost all variations of covering by rectangles are NP-hard.

The boundary structure of your example provides some constraints on the one fixed side length of the rectangle $R$. The short boundary segment $s$ at the top-right limits $R$ to have one side ${\le} |s|$.

My guess is that ad-hoc reasoning supplemented with guess & check might suffice. Pin the one side to ${=} |s|$ and then cover your polygon by stretching the other side length as far as possible in each placement. See below for an attempt. Linear programming seems overkill if you want to solve the problem just for this one example.

---

         

---