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:
- 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.
- 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:
(After a single SPLIT of any of the long rectangles at the obvious spot, the union can be finished with a sequence of JOINs.)