4
$\begingroup$

Suppose that there are rectangles in the Cartesian plane, each aligned with the axes---the rectangles are defined by left and right x-coordinates and top and bottom y-coordinates.

There are two operations on rectangles:

  1. SPLIT partitions a single rectangle into two adjacent rectangles with either a horizontal or vertical cut. Splitting is parameterized with an $x$ or $y$ value indicating where to split.
  2. JOIN is the inverse of SPLIT, turning two adjacent, non-overlapping, aligned rectangles of the same height or width into a single rectangle.

Question: Given a set of N non-overlapping rectangles whose union is a (larger) rectangle---the set forms a partition of the larger rectangle---is there an efficient algorithm that will compute the shortest sequence of SPLIT and JOIN operations to transform the set of rectangles into the single (union) rectangle?

The smallest partition that requires using a SPLIT to transform a partition into the union is this:

enter image description here

(After a single SPLIT of any of the long rectangles at the obvious spot, the union can be finished with a sequence of JOINs.)

$\endgroup$
  • $\begingroup$ One answer may be to do all possible splits, and then using dynamic programming to find how to reassemble the rectangle with minimum cost. You should keep track of the split rectangles and subtract the cost when reassembling the same rectangles. Runtime tends to be exponential in the dimensions of the rectangle, however using memory/Dynamic-Programming may make the solution polynomial. $\endgroup$ – narek Bojikian Jul 3 '18 at 19:25
  • $\begingroup$ I think a useful representation for partial solutions is to first "complete the grid": turn each 3-way junction into a 4-way junction by adding a line segment of a different colour, say red. Repeat this until every junction is a 4-way junction. These red line segments represent the complete set of "possible cuts" that are currently absent, but which may be added by a SPLIT. $\endgroup$ – j_random_hacker Jul 4 '18 at 13:20
  • $\begingroup$ For speeding up an exhaustive search, I can suggest: (1) In the absence of 4-way junctions, every JOIN reduces the number of line segments by exactly 3 (the segment joined disappears, and at each end 2 segments become 1), so if you have already found a solution meeting this bound, you know you can prune the search at this point; (2) the last move in any optimal solution is necessarily a JOIN between 2 rectangles that are either full-height or full-width, suggesting a recursive strategy in which we proceed in reverse order, first trying each vertical or horizontal "guillotine cut". $\endgroup$ – j_random_hacker Jul 4 '18 at 13:22

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.