optimal negative space between rectangles algorithm?

Question

Given rectangles r[ ] inside of larger rectangle R, is there an optimal speedy algorithm for determining the minimum number of rectangles that fill in the "negative space" between r[ ]?

For example, given these three blue rectangles inside of the purple rectangle:

How could I quickly determine a list of rectangles like these in green below (which may not be the optimal configuration, hence my post):

Answer 1

What oosterwal describes is a special case of trapezoidal decomposition, a well-understood primitive in computational geometry typically used for point location in a planar subdivision. It can be implemented in time O(n log n) with a reasonable constant.

When the rectangles are in general position, it will return a "rectangulation" with # green rectangles = 3 * # blue rectangles + 1, and this is optimal. The L-shaped neighborhood of each blue corner must be cut in one direction or the other by a green segment (general position: we can't use the same segment for two blue rectangles), so for each blue rectangle, we add 4 green edges 8 green edges and 4 vertices (4 new edges plus 4 subdivided), decreasing the number of connected components by 1 in the process. The result by the polyhedral formula is 3 more faces (rectangles):

V - E + F = 1 + # connected components.

---

Example:

 0123456789abc
0+-----------+
1|           |
2|  +--+     |
3|  |R | +-+ |
4|  +--+ |S| |
5|       | | |
6| +--+  | | |
7| |T |  +-+ |
8| +--+      |
9+-----------+

We're running a sweep line from top to bottom. The events are

# (y, whichside, xmin, xmax)
(2, top, 3, 6)  # R
(3, top, 8, a)  # S
(4, bot, 3, 6)  # R
(6, top, 2, 5)  # T
(7, bot, 8, a)  # S
(8, bot, 2, 5)  # T

We set up a binary search tree ordered by x that holds the partially constructed green rectangles. I'll write it as a list.

# (xmin, xmax, ymin)
(0, c, 0)

Now we start processing events. First is (2, top, 3, 6). We find that it's nested inside the only green rectangle so far, (xmin=0, xmax=c, ymin=0, ymax=2). (The blue interval always nests as long as the blue rectangles don't intersect.) We start two new green rectangles, one on each side of the blue rectangle, and the search tree contains

(0, 3, 2) (6, c, 2)

Now we process (3, top, 8, a). The interval (8, a) nests inside (6, c), so we finish another rectangle (xmin=6, xmax=c, ymin=2, ymax=3) and start two more:

(0, 3, 2) (6, 8, 3) (a, c, 3)

Now we process (4, bot, 3, 6). This ends the green rectangles to its left and right, (xmin=0, xmax=3, ymin=2, ymax=4) and (xmin=6, xmax=8, ymin=3, ymax=4). The search tree is

(0, 8, 4) (a, c, 3)

I think things should be clear by this point. Here is the finished rectangulation:

 0123456789abc
0+-----------+
1|           |
2+--+--+-----|
3|  |R |-+-+-|
4+--+--+-|S| |
5|       | | |
6+-+--+--+ | |
7| |T +--+-+-+
8+-+--+------+
9+-----------+

A note on handling degeneracies: put bottom events before top events with the same y-coordinate, and suppress rectangles with zero area. There will still be "unnecessary" rectangles in general, which a more sophisticated event processor could avoid (by handling all events at a given y-coordinate at once).