Theoretical Complexity of Grid Cover Problems Used in Radar Applications

Yann Briheche (), Frederic Barbaresco (), Fouad Bennis () and Damien Chablat ()
Additional contact information
Yann Briheche: Thales Air Systems
Frederic Barbaresco: Thales Air Systems
Fouad Bennis: Laboratoire des Sciences du Numérique de Nantes, UMR CNRS 6004
Damien Chablat: Laboratoire des Sciences du Numérique de Nantes, UMR CNRS 6004

Journal of Optimization Theory and Applications, 2018, vol. 179, issue 3, No 19, 1086-1106

Abstract: Abstract Modern radars are highly flexible systems, relying on digital antennas to dynamically control the radar beam shape and position through electronic circuits. Radar surveillance is performed by sequential emission of different radar beams. Optimization of radar surveillance requires finding a minimal subset of radar beams, which covers and ensures detection over the surveillance space, among a collection of available radar beams with different shapes and positions, thus minimizing the required scanning time. Optimal radar surveillance can be modelled by grid covering, a specific geometric case of set covering where the universe set is laid out on a grid, representing the radar surveillance space, which must be covered using available subsets, representing the radar beams detection areas. While the set cover problem is generally difficult to solve optimally, certain geometric cases can be optimized in polynomial time. This paper studies the theoretical complexity of grid cover problems used for modelling radar surveillance, proving that unidimensional grids can be covered by strongly polynomial algorithms based on dynamic programming, whereas optimal covering of bidimensional grids is generally non-deterministic polynomially hard.

Keywords: Set cover problem; Grid covering; Combinatorial optimization; NP-hardness; Radar resource management; 05B40; 52C15; 90C39 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-018-1354-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:joptap:v:179:y:2018:i:3:d:10.1007_s10957-018-1354-x

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-018-1354-x

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().