Optimal negative space between rectangles algorithm?

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).

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).

This looks really cool and I've love to see some more detail about it. – templatetypedef Feb 14 at 4:07 As oosterwal said, you can perform a plane sweep by sorting and processing the blue horizontal segments from top to bottom. When you encounter a blue top, terminate the green rectangle above it and begin two more.

When you encounter a blue bottom, terminate the green rectangles to the left and right and begin a new one. Each of these operations is O(log n) with a binary tree storing the active green rectangles in order of x coordinate. Handling the degenerate cases is sort of a pain though... – a dabbler Feb 14 at 4:28 OK, it's a bit sloppy to say that # connected components always decreases by 1.

However, it does always go from # blue rectangles + 1 in the beginning to 1 at the end, so the math still works; we just have to amortize. – a dabbler Feb 14 at 4:36 I would benefit from some high level pseudo-code... having a tough time parsing this answer. – jedierikb Feb 14 at 22:22 Got it -- great explanation.

Thank you. Much appreciated. – jedierikb Feb 147 at 1:49.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.