Robust Designs for Circle Coverings of a Square

Mihály Csaba Markót ()
Additional contact information
Mihály Csaba Markót: University of Vienna

Chapter Chapter 11 in Optimized Packings with Applications, 2015, pp 225-242 from Springer

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

Keywords: Circle covering; Uncertainty; Sensor network deployment; Robust design; Global optimization; Interval arithmetic; Complete search; Black box search (search for similar items in EconPapers)
Date: 2015
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-18899-7_11

Ordering information: This item can be ordered from
http://www.springer.com/9783319188997

DOI: 10.1007/978-3-319-18899-7_11

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().