Covering convex regions with unit discs

Seminar
Speaker
Simi Haber (Bar-Ilan University)
Date
03/01/2021 - 15:30 - 14:00Add to Calendar 2021-01-03 14:00:00 2021-01-03 15:30:00 Covering convex regions with unit discs Given a convex region C in the plane, how many unit discs are needed to cover it? This classic discrete geometry problem has real life applications in, e.g., placing cellular antennas.   A precise answer for the above question seems out of reach, even when C is a disc of a given radius. However, Blaschke, Toth and Hadwiger provided a nonconstructive upper bound for the number of required discs, as a function of the area and perimeter of C. In this talk we will discuss an improved upper bound, an algorithm achieving this bound, and a lower bound showing the algorithm is asymptotically tight for fat regions. Based on joint work with Reuven Cohen and Shai Gul. Zoom אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Zoom
Abstract
Given a convex region C in the plane, how many unit discs are needed to cover it? This classic discrete geometry problem has real life applications in, e.g., placing cellular antennas.
 
A precise answer for the above question seems out of reach, even when C is a disc of a given radius. However, Blaschke, Toth and Hadwiger provided a nonconstructive upper bound for the number of required discs, as a function of the area and perimeter of C.

In this talk we will discuss an improved upper bound, an algorithm achieving this bound, and a lower bound showing the algorithm is asymptotically tight for fat regions.

Based on joint work with Reuven Cohen and Shai Gul.

Last Updated Date : 31/12/2020