Covering in the Plane

Speaker
Shai Gul - BIU
Date
18/01/2015 - 14:00 - 13:00Add to Calendar 2015-01-18 13:00:00 2015-01-18 14:00:00 Covering in the Plane We consider the problem of efficiently covering a domain by unit discs. This problem has applications in optimal cellular antennae placement, facility location any many other similar problems. Our main interest is a result by W. Blaschke, which determines an upper bound to the number of unit discs which are needed to cover a given convex domain . Blaschke showed that a domain can be covered with  2A/3 sqrt(3) + 2L/ pi sqrt(3) + 1  (1)  unit circles, where A is the area of the given domain and L the perimeter. This result is due to the properties of the hexagonal lattice. This talk will be composed of three main results. First, we will show that in special cases Blaschke's result can be improved and then show how to locate the hexagonal lattice in these cases. Second, we will give a sufficient condition under which (1) can be improved. Third, we will give an algorithmic approach which determines the exact position of the hexagonal lattice, such that the number of unit hexagons (in the hexagonal lattice) which hit the domain is minimized. Building 216, Room 201 אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Building 216, Room 201
Abstract

We consider the problem of efficiently covering a domain by unit discs. This problem has applications in optimal cellular antennae placement, facility location any many other similar problems. Our main interest is a result by W. Blaschke, which determines an upper bound to the number of unit discs which are needed to cover a given convex domain . Blaschke showed that a domain can be covered with  2A/3 sqrt(3) + 2L/ pi sqrt(3) + 1  (1)  unit circles, where A is the area of the given domain and L the perimeter. This result is due to the properties of the hexagonal lattice. This talk will be composed of three main results. First, we will show that in special cases Blaschke's result can be improved and then show how to locate the hexagonal lattice in these cases. Second, we will give a sufficient condition under which (1) can be improved. Third, we will give an algorithmic approach which determines the exact position of the hexagonal lattice, such that the number of unit hexagons (in the hexagonal lattice) which hit the domain is minimized.

Last Updated Date : 13/01/2015