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.
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
