BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/979
DTSTAMP:20230914T125945Z
SUMMARY:Murdering Squares and Rectangles using Guillotines
DESCRIPTION:Speaker: Kshitij Gajjar\n\nAbstract: \nAbstract: A bunch of di
sjoint 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 a
xis-parallel guillotine cuts such that each rectangle is in a different pi
ece 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 f
ollowing results.\n(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.\n(ii) If all the rectangles are squares\, then there is a seri
es of guillotine cuts such that at least n/68 squares survive in the end.\
nTime permitting\, we will see that if the fraction in the first result ca
n be improved to n/c (for some constant c)\, then it would imply a solutio
n to a longstanding open problem in theoretical computer science.\n
URL:https://www.tcs.tifr.res.in/web/events/979
DTSTART;TZID=Asia/Kolkata:20190801T160000
DTEND;TZID=Asia/Kolkata:20190801T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR