On the computational cost of the set cover approach for the optimal camera placement problem and possible set-cover-inspired trade-offs for surveillance infrastructure design

IRIMAS, Université de Haute-Alsace, 12 Rue des Frères Lumière, 68 093 Mulhouse, France

^* Corresponding author: julien.kritter@uha.fr

Received: 9 December 2019
Accepted: 17 June 2021

Abstract

The 𝒩𝒫-hard minimum set cover problem (SCP) is a very typical model to use when attempting to formalise optimal camera placement (OCP) applications. In a generic form, the OCP problem relates to the positioning of individual cameras such that the overall network is able to cover a given area while meeting a set of application-specific requirements (image quality, redundancy, ...) and optimising an objective, typically minimum cost or maximum coverage. In this paper, we focus on an application called global or persistent surveillance: camera networks which ensure full coverage of a given area. As preliminary work, an instance generation pipeline is proposed to create OCP instances from real-world data and solve them using existing literature. The computational cost of both the instance generation process and the solving algorithms however highlights a need for more efficient methods for decision makers to use in real-world settings. In this paper, we therefore propose to review the suitability of the approach, and more specifically to question two key elements: the impact of sampling frequencies and the importance of rigid full-coverage constraints. The results allow us to quickly provide decision makers with an overview of available solutions and trade-offs.