שלחו לחבר

Covering convex regions with unit discs

Seminar
Speaker
Simi Haber (Bar-Ilan University)
Date
03/01/2021 - 15:30 - 14:00
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.

תאריך עדכון אחרון : 31/12/2020