Murdering Squares and Rectangles using Guillotines

Abstract: A bunch of disjoint axis-parallel rectangles are drawn on a single piece of paper. The aim is to divide the paper into several smaller pieces using a series of axis-parallel guillotine cuts such that each rectangle is in a different piece of paper at the end of all the slashing. Some rectangles might die in the process; if a guillotine cut is made across the body of a rectangle, then that rectangle is killed. In this talk, we will see proofs of the following results.

(i) For every configuration of n rectangles, there is a series of guillotine cuts such that at least n/log n rectangles survive in the end.

(ii) If all the rectangles are squares, then there is a series of guillotine cuts such that at least n/68 squares survive in the end.

Time permitting, we will see that if the fraction in the first result can be improved to n/c (for some constant c), then it would imply a solution to a longstanding open problem in theoretical computer science.