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.