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