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.

« December 2022 »
December
MoTuWeThFrSaSu
1234
567891011
12131415161718
19202122232425
262728293031
Upcoming Events
RISC Forum Dec 12, 2022 01:30 PM - 01:45 PM
NO RISC Forum Dec 19, 2022 01:30 PM - 01:55 PM
NO RISC Forum Dec 26, 2022 01:30 PM - 01:45 PM
NO RISC Forum Jan 02, 2023 01:30 PM - 01:45 PM
RISC Forum Jan 09, 2023 01:30 PM - 01:50 PM
Previous events…
Upcoming events…