Tata Institute of Fundamental Research

Murdering Squares and Rectangles using Guillotines

STCS Student Seminar
Speaker: Kshitij Gajjar
Organiser: Phani Raj Lolakapuri
Date: Thursday, 1 Aug 2019, 16:00 to 17:00
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  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.