Campus Event Calendar
Event Entry
What and Who
Geometric Separators, and Packing and Piercing for Fat Objects
Edgar Ramos
Max-Planck-Institut für Informatik - AG 1
AG1 Mittagsseminar (others' work)
AG 1, AG 2, AG 3, AG 4
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 25 February 2002
13:30
45 Minutes
46.1 - MPII
024
Saarbrücken
Abstract
I'll show the following result of Smith and Wormald '88:
Given n disjoint squares in the plane, there is a rectangle such
that inside or outside there are at most 2n/3 squares, and
intersecting the boundary there are O(sqrt(n)) squares.
Then show how Chan '01 used this sort of separator to obtain
a PTAS for packing and piercing of fat objects.
Contact
Edgar A. Ramos
--email hidden
passcode not visible
logged in users only