Robust Designs for Circle Coverings of a Square

In this chapter we investigate coverings of a square with uniform circles of minimal radius, with uncertainties in the actual locations of the circles. This setting is an example model of deploying sensors or other kind of observation units so that there are uncertainties in their deployments. Possible examples include scenarios when the deployment has to be made remotely (e.g., from the air) into a potentially dangerous place, deployments into a location with unknown terrain, or deployments influenced by the weather. Our goal is to produce coverings that are optimal in terms of a minimal radius, and are also robust in the following sense: wherever the circles are actually placed within a given uncertainty region, the result is still guaranteed to be a covering. We investigate three special uncertainty regions: first we prove that for uniform circular uncertainty regions the optimal robust covering can be created from the exact optimal covering without uncertainties, provided that the exact covering configuration is feasible for the robust scenario. For uncertainty regions given by line segments and by general convex polygons we design a bi-level optimization method combining a complete and rigorous global search and a derivative free black-box search, and show the efficiency of the method on some examples.