Personal tools
You are here: Home / Internal / RISC Forum / 2010 / RISC Forum

RISC Forum

Prof. Pedro Ramos: Covering Decomposition
When Apr 12, 2010
from 01:30 PM to 02:30 PM
Where Seminar Room
Add event to calendar vCal
iCal

A family F of subsets of the plane is a k-covering of S if every point of S is covered by at least k sets of F. The covering decomposition problem can be stated as follows: under which conditions can we guarantee that a k-covering can be decomposed into 2 independent coverings, or, more generally, into j independent coverings? Despite some intensive work in the last few years, fundamental questions are still unknown. For instance, no bound for k is known for the basic problem when F is a set of unit disks. In this talk we review some of the results in this area and present the following theorem: If F is a family of congruent copies of a centrally symmetric polygon P, then a k-covering of S can be decomposed into \Omega(\sqrt{k}) independent coverings.

Joint work with Greg Aloupis, Jean Cardinal, Sebastian Colette,
Stefan Langerman, David Orden.

« March 2024 »
March
MoTuWeThFrSaSu
123
45678910
11121314151617
18192021222324
25262728293031
Upcoming Events
RISC Forum Mar 04, 2024 01:30 PM - 01:45 PM
RISC Forum Mar 11, 2024 01:30 PM - 01:45 PM
RISC Forum Mar 18, 2024 01:30 PM - 01:45 PM
NO RISC Forum Mar 25, 2024 01:30 PM - 01:45 PM
NO RISC Forum Apr 01, 2024 01:30 PM - 01:45 PM
Previous events…
Upcoming events…