2
$\begingroup$

I have a 𝑛×𝑚 rectangular grid of cells, and a set 𝑅 of rectangles within this grid. Each rectangle is a subset of the cells. (Alternatively, you can think of them as axis-aligned rectangles where each of the four corners has integer coordinates.) Some of these rectangles overlap and some of these rectangles are adjacent. I want to merge adjacent rectangles to bigger rectangles if possible and remove overlaps.

So my output set should have bigger non overlapping rectangles instead of small adjacent or overlapping rectangles. The number of rectangles in the output set should be minimized. The output set need not be a subset of input set. Is there any approximate or exact algorithm for this problem?

Improve this question
$\endgroup$
6
  • $\begingroup$ Does the output set need to be a subset of the input, or can we freely choose rectangles not in the input? If we can freely choose them, then your problem boils down to finding a minimum set of rectangles that partition a given orthogonal polygon. $\endgroup$
    – Discrete lizard ♦
    Jul 18, 2021 at 14:31
  • $\begingroup$ One approach could be to iteratively choose a free convex corner in the polygon, add the maximum size rectangle that contains this corner and fits in the polygon. This gives a minimum set of rectangles whose union is the polygon, but the rectangles may overlap. Then, for each area with overlap, choose a rectangle that covers it, and cut the others in two. This gives a partition, which I think would be optimal if the second step is done optimally, but I'm not sure. $\endgroup$
    – Discrete lizard ♦
    Jul 18, 2021 at 14:31
  • $\begingroup$ How do you represent your input and output? You could think of your cells as vertices in a simple graph, and for each rectangle connect all its vertices (i.e. its cells). Then you only need to find all components in the graph. This should be doable in $O(|R| \cdot m \cdot n)$. $\endgroup$
    – idmean
    Jul 18, 2021 at 16:03
  • $\begingroup$ @Discretelizard how to create orthogonal polygon given an input set of rectangles. $\endgroup$
    – thambi
    Jul 19, 2021 at 4:03
  • $\begingroup$ @idmean currently its represented using Cartesian coordinates of top left and bottom right corner of rectangle.Graph approach is a nice solution. But I am a bit worried that an algorithm where each cell is considered will have a higher memory peak than an algorithm with rectangles. $\endgroup$
    – thambi
    Jul 19, 2021 at 4:06

1 Answer 1

Reset to default
3
$\begingroup$

Take a look at this paper. You can interpret each coordinate pair in your grid that is part of at least one input rectangle as being part of a polygon $P$, and every coordinate pair that does not belong to any input rectangles as not being part of $P$.

Then the problem becomes partitioning $P$ into the smallest number of non-overlapping rectangles. The referenced paper provides a polynomial-time algorithm.

Interestingly, the problem becomes $\mathsf{NP}$-hard when the output rectangles are allowed to overlap. See the discussion in this paper and the references therein.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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